oj.uz

Submission #429217

# Submission time Handle Problem Language Result Execution time Memory
429217 2021-06-15T19:04:59 Z CrouchingDragon Werewolf (IOI18_werewolf) C++17
100 / 100
 897 ms 79616 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int M = (int)size(X), Q = (int)size(S);
    vector<vi> left(N), right(N);
    for (int j = 0; j < M; ++j) {
        int u = X[j], v = Y[j];
        if (u > v) swap(u, v);
        left[v].push_back(u);
        right[u].push_back(v);
    }
    vi pl(N, N), pr(N, -1), p;
    auto find = [&](auto& self, int u, int lb, int ub) -> int {
        return p[u] < lb || ub < p[u] ? u : p[u] = self(self, p[u], lb, ub);
    };
    p = pl;
    for (int u = 0; u < N; ++u) {
        for (auto v : left[u]) {
            v = find(find, v, 0, N - 1);
            if (v != u) p[v] = pl[v] = u;
        }
    }
    p = pr;
    for (int u = N - 1; u >= 0; --u) {
        for (auto v : right[u]) {
            v = find(find, v, 0, N - 1);
            if (v != u) p[v] = pr[v] = u;
        }
    }
    vector<vi> F(N);
    for (int u = 0; u < N; ++u) {
        if (int v = pr[u]; v != -1) F[v].push_back(u);
    }
    vi l(N), r(N);
    int timer = 0;
    auto tour = [&](auto& self, int u) -> void {
        l[u] = timer;
        for (auto v : F[u]) self(self, v);
        r[u] = timer++;
    };
    for (int u = 0; u < N; ++u) {
        if (pr[u] == -1) tour(tour, u);
    }
    vi subleft(Q), subright(Q), I(Q);
    iota(begin(I), end(I), 0);
    p = pl;
    sort(begin(I), end(I), [&](int q1, int q2){ return R[q1] < R[q2]; });
    for (auto q : I) subleft[q] = find(find, E[q], 0, R[q]);
    p = pr;
    sort(begin(I), end(I), [&](int q1, int q2){ return L[q1] > L[q2]; });
    for (auto q : I) subright[q] = find(find, S[q], L[q], N - 1);
    vector<vi> queries(N);
    for (auto q : I) {
        if (int u = subleft[q]; u <= R[q]) queries[u].push_back(q);
    }
    vector<set<int>> T(N);
    vi ans(Q);
    for (int u = 0; u < N; ++u) {
        T[u].insert(r[u]);
        for (auto q : queries[u]) {
            int v = subright[q];
            auto iter = T[u].lower_bound(l[v]);
            if (iter != end(T[u]) && *iter <= r[v]) ans[q] = 1;
        }
        if (int v = pl[u]; v < N) {
            if (size(T[v]) < size(T[u])) swap(T[v], T[u]);
            T[v].merge(T[u]);
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 296 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 6 ms 1452 KB Output is correct
11 Correct 7 ms 1368 KB Output is correct
12 Correct 7 ms 1328 KB Output is correct
13 Correct 8 ms 1452 KB Output is correct
14 Correct 7 ms 1356 KB Output is correct
15 Correct 7 ms 1476 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 70620 KB Output is correct
2 Correct 663 ms 69980 KB Output is correct
3 Correct 636 ms 68888 KB Output is correct
4 Correct 679 ms 69008 KB Output is correct
5 Correct 698 ms 69012 KB Output is correct
6 Correct 784 ms 69584 KB Output is correct
7 Correct 836 ms 69304 KB Output is correct
8 Correct 647 ms 70084 KB Output is correct
9 Correct 593 ms 69032 KB Output is correct
10 Correct 561 ms 68440 KB Output is correct
11 Correct 588 ms 68676 KB Output is correct
12 Correct 637 ms 68552 KB Output is correct
13 Correct 646 ms 79580 KB Output is correct
14 Correct 711 ms 79616 KB Output is correct
15 Correct 694 ms 79460 KB Output is correct
16 Correct 671 ms 79452 KB Output is correct
17 Correct 780 ms 69328 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 6 ms 1452 KB Output is correct
11 Correct 7 ms 1368 KB Output is correct
12 Correct 7 ms 1328 KB Output is correct
13 Correct 8 ms 1452 KB Output is correct
14 Correct 7 ms 1356 KB Output is correct
15 Correct 7 ms 1476 KB Output is correct
16 Correct 897 ms 70620 KB Output is correct
17 Correct 663 ms 69980 KB Output is correct
18 Correct 636 ms 68888 KB Output is correct
19 Correct 679 ms 69008 KB Output is correct
20 Correct 698 ms 69012 KB Output is correct
21 Correct 784 ms 69584 KB Output is correct
22 Correct 836 ms 69304 KB Output is correct
23 Correct 647 ms 70084 KB Output is correct
24 Correct 593 ms 69032 KB Output is correct
25 Correct 561 ms 68440 KB Output is correct
26 Correct 588 ms 68676 KB Output is correct
27 Correct 637 ms 68552 KB Output is correct
28 Correct 646 ms 79580 KB Output is correct
29 Correct 711 ms 79616 KB Output is correct
30 Correct 694 ms 79460 KB Output is correct
31 Correct 671 ms 79452 KB Output is correct
32 Correct 780 ms 69328 KB Output is correct
33 Correct 825 ms 70008 KB Output is correct
34 Correct 347 ms 22572 KB Output is correct
35 Correct 887 ms 71916 KB Output is correct
36 Correct 867 ms 70896 KB Output is correct
37 Correct 827 ms 71340 KB Output is correct
38 Correct 789 ms 71252 KB Output is correct
39 Correct 888 ms 70912 KB Output is correct
40 Correct 847 ms 76276 KB Output is correct
41 Correct 709 ms 69540 KB Output is correct
42 Correct 662 ms 69120 KB Output is correct
43 Correct 871 ms 75440 KB Output is correct
44 Correct 731 ms 70192 KB Output is correct
45 Correct 801 ms 72144 KB Output is correct
46 Correct 781 ms 71652 KB Output is correct
47 Correct 663 ms 79492 KB Output is correct
48 Correct 718 ms 79388 KB Output is correct
49 Correct 730 ms 79536 KB Output is correct
50 Correct 637 ms 79588 KB Output is correct
51 Correct 786 ms 75308 KB Output is correct
52 Correct 856 ms 75196 KB Output is correct