QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91725#5504. Flower GardenDenisovWA 10148ms147852kbC++206.2kb2023-03-29 14:43:352023-03-29 14:43:39

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 14:43:39]
  • 评测
  • 测评结果:WA
  • 用时:10148ms
  • 内存:147852kb
  • [2023-03-29 14:43:35]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = -1, inf = 1000111222;


vector <pii> e;
int n;

vector <int> t, t1;

inline void upd (int v, int tl, int tr, int l, int r, int id, bool from) {
    if (l > r) return;
    if (tl == l && tr == r) {
        if (from) {
            e.pb({id, t1[v]});
        }
        else {
            e.pb({t[v], id});
        }
        return;
    }
    int tm = (tl + tr) >> 1;
    upd(v << 1, tl, tm, l, min(r, tm), id, from);
    upd(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, id, from);
}
int mx;


inline int build (int v, int tl, int tr) {
    umax(mx, 3 * n + v + 1);
    t[v] = 3 * n + v;
    if (tl == tr) {
        e.pb({tr, 3 * n + v});
        return 3 * n + v;
    }
    int tm = (tl + tr) >> 1;
    int L = build(v << 1, tl, tm);
    int R = build(v << 1 | 1, tm + 1, tr);
    e.pb({L, 3 * n + v});
    e.pb({R, 3 * n + v});
    return 3 * n + v;
}

inline int build1 (int v, int tl, int tr) {
    t1[v] = mx++;
    if (tl == tr) {
        e.pb({t1[v], tr});
        return t1[v];
    }
    int tm = (tl + tr) >> 1;
    int L = build1(v << 1, tl, tm);
    int R = build1(v << 1 | 1, tm + 1, tr);
    e.pb({t1[v],L});
    e.pb({t1[v],R});
    return t1[v];
}

vector <vector <int> > g, gr;
vector <int> used, order, cl, w;

inline void dfs (int v) {
    used[v] = 1;
    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
    order.pb(v);
}

inline void dfs1 (int v, int c) {
    used[v] = 2;
    cl[v] = c;
    w[c] += v < 3 * n;
    for (int to : gr[v]) {
        if (used[to] == 1) {
            dfs1(to, c);
        }
    }
}

inline int go (int v) {
    int ans = w[v];
    for (int to : g[v]) {
        ans += go(to);
    }
    return ans;
}

vector <int> ans;

inline void color (int v) {
    ans[v] = 1;
    for (int to : g[v]) {
        color(to);
    }
}

inline void color1 (int v) {
    ans[v] = 0;
    for (int to : gr[v]) {
        color1(to);
    }
}

inline void test_case () {
    for (auto &i : g) i.clear();
    for (auto &i : gr) i.clear();
    g.clear();
    ans.clear();
    gr.clear();
    t.clear();
    t1.clear();
    cl.clear();
    w.clear();
    used.clear();
    order.clear();
    e.clear();
    mx = 0;
    int q;
    cin >> n >> q;
    t.resize(3 * 4 * n);
    t1.resize(3 * 4 * n);
    build(1, 0, 3 * n - 1);
    build1(1, 0, 3 * n - 1);
    for (int i = 0, a, b, c, d; i < q; i++) {
        cin >> a >> b >> c >> d;
        --a, --b, --c, --d;
        int cur = mx;
        upd(1, 0, 3 * n - 1, c, d, cur, false);
        upd(1, 0, 3 * n - 1, a, b, cur, true);
        ++mx;
    }
    //LOG("here");
    int N = mx;
    gr.resize(N);
    g.resize(N);
    for (auto &i : e) {
        g[i.first].pb(i.second);
        gr[i.second].pb(i.first);
    }
    used.resize(N);
    for (int i = 0; i < N; i++) {
        if (!used[i]) {
            dfs(i);
        }
    }
    reverse(all(order));
    w.resize(N);
    cl.resize(N);
    int cmp = 0;
    for (int i : order) {
        if (used[i] == 1) {
            dfs1(i, cmp);
            ++cmp;
        }
    }
    for (int i = 0; i < cmp; i++) {
        if (w[i] > 2 * n) {
            cout << "NIE\n";
            return;
        }
    }
    for (auto &i : g) i.clear();
    for (auto &i : gr) i.clear();
    g.clear();
    gr.clear();
    gr.resize(cmp);
    g.resize(cmp);
    for (auto &i : e) {
        if (cl[i.first] != cl[i.second]) {
            g[cl[i.first]].pb(cl[i.second]);
            gr[cl[i.second]].pb(cl[i.first]);
        }
    }
    cout << "TAK\n";
    ans.resize(cmp);
    /// 1 - rose
    /// 0 - violet
    for (int i = 0; i < cmp; i++) {
        if (w[i] > n) {
            int res = go(i);
            if (res <= 2 * n) {
                color(i);
                string answer(3 * n, 'F');
                for (int j = 0; j < 3 * n; j++) {
                    if (ans[cl[j]]) {
                        answer[j] = 'R';
                    }
                }
                cout << answer << '\n';
                return;
            }
            ans.assign(cmp, 1);
            color1(i);
            string answer(3 * n, 'R');
            for (int j = 0; j < 3 * n; j++) {
                if (!ans[cl[j]]) {
                    answer[j] = 'F';
                }
            }
            cout << answer << '\n';
            return;
        }
    }
    order.clear();
    used.clear();
    used.resize(cmp);
    for (int i = 0; i < cmp; i++) {
        if (!used[i]) {
            dfs(i);
        }
    }
    int s = 0;
    for (int v : order) {
        s += w[v];
        ans[v] = 1;
        if (s >= n) {
            assert(s <= 2 * n);
            break;
        }
    }
    string answer(3 * n, 'F');
    for (int i = 0; i < 3 * n; i++) {
        if (ans[cl[i]]) {
            answer[i] = 'R';
        }
    }
    cout << answer << '\n';
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    for (int test = 1; test <= t; test++) {
        test_case();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3464kb

input:

2
1 3
1 1 2 2
1 2 3 3
1 1 3 3
1 3
1 1 2 2
2 2 3 3
3 3 1 1

output:

TAK
RFF
NIE

result:

ok good!

Test #2:

score: 0
Accepted
time: 10148ms
memory: 147852kb

input:

10
33333 100000
28701 40192 93418 95143
95902 97908 78378 78461
36823 44196 22268 23996
23977 24786 33315 48829
83965 90411 4923 8445
20235 21177 32543 47454
29598 35414 72477 73049
2014 12632 42163 46466
64305 65518 98825 99552
32331 41625 92772 96224
26500 54122 76990 77126
18249 20335 31165 36080...

output:

NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE

result:

ok good!

Test #3:

score: -100
Wrong Answer
time: 9570ms
memory: 123544kb

input:

10
33333 100000
15207 33614 66276 66276
97173 97173 67589 73960
19673 36626 65207 65207
89825 98169 27079 27079
56067 56966 7560 7560
18170 35477 18752 18752
32621 36748 34460 34460
61595 61700 14117 14117
32395 36710 9064 9064
13172 13172 1728 4640
40462 41878 47171 47171
76965 82414 5767 5767
9225...

output:

TAK
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

result:

wrong answer odpowiedz ma za malo/duzo roz!