oj.uz

Submission #429207

# Submission time Handle Problem Language Result Execution time Memory
429207 2021-06-15T18:55:40 Z CrouchingDragon Werewolf (IOI18_werewolf) C++17
100 / 100
 1064 ms 87480 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<vector<int>> 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);
    }
    vector<int> pl(N, N), pr(N, -1), p(N);
    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);
    };
    fill(begin(p), end(p), N);
    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;
        }
    }
    fill(begin(p), end(p), -1);
    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<vector<int>> F(N);
    for (int u = 0; u < N; ++u) {
        int v = pr[u];
        if (v != -1) F[v].push_back(u);
    }
    vector<int> 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);
    }
    vector<int> 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<vector<int>> queries(N);
    for (auto q : I) {
        int u = subleft[q], v = subright[q];
        if (L[q] <= v && u <= R[q]) queries[u].push_back(q);
    }
    vector<set<int>> T(N);
    vector<int> 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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 9 ms 1356 KB Output is correct
11 Correct 7 ms 1356 KB Output is correct
12 Correct 7 ms 1360 KB Output is correct
13 Correct 7 ms 1436 KB Output is correct
14 Correct 6 ms 1356 KB Output is correct
15 Correct 7 ms 1460 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 873 ms 72536 KB Output is correct
2 Correct 651 ms 77868 KB Output is correct
3 Correct 663 ms 76788 KB Output is correct
4 Correct 680 ms 76796 KB Output is correct
5 Correct 676 ms 76776 KB Output is correct
6 Correct 831 ms 77436 KB Output is correct
7 Correct 929 ms 77132 KB Output is correct
8 Correct 738 ms 77892 KB Output is correct
9 Correct 615 ms 76800 KB Output is correct
10 Correct 586 ms 76308 KB Output is correct
11 Correct 630 ms 76684 KB Output is correct
12 Correct 707 ms 76400 KB Output is correct
13 Correct 744 ms 87252 KB Output is correct
14 Correct 862 ms 87228 KB Output is correct
15 Correct 758 ms 87284 KB Output is correct
16 Correct 687 ms 87304 KB Output is correct
17 Correct 971 ms 77100 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 9 ms 1356 KB Output is correct
11 Correct 7 ms 1356 KB Output is correct
12 Correct 7 ms 1360 KB Output is correct
13 Correct 7 ms 1436 KB Output is correct
14 Correct 6 ms 1356 KB Output is correct
15 Correct 7 ms 1460 KB Output is correct
16 Correct 873 ms 72536 KB Output is correct
17 Correct 651 ms 77868 KB Output is correct
18 Correct 663 ms 76788 KB Output is correct
19 Correct 680 ms 76796 KB Output is correct
20 Correct 676 ms 76776 KB Output is correct
21 Correct 831 ms 77436 KB Output is correct
22 Correct 929 ms 77132 KB Output is correct
23 Correct 738 ms 77892 KB Output is correct
24 Correct 615 ms 76800 KB Output is correct
25 Correct 586 ms 76308 KB Output is correct
26 Correct 630 ms 76684 KB Output is correct
27 Correct 707 ms 76400 KB Output is correct
28 Correct 744 ms 87252 KB Output is correct
29 Correct 862 ms 87228 KB Output is correct
30 Correct 758 ms 87284 KB Output is correct
31 Correct 687 ms 87304 KB Output is correct
32 Correct 971 ms 77100 KB Output is correct
33 Correct 870 ms 77808 KB Output is correct
34 Correct 328 ms 33700 KB Output is correct
35 Correct 1002 ms 80184 KB Output is correct
36 Correct 1064 ms 78812 KB Output is correct
37 Correct 861 ms 79364 KB Output is correct
38 Correct 884 ms 79428 KB Output is correct
39 Correct 894 ms 78632 KB Output is correct
40 Correct 949 ms 87196 KB Output is correct
41 Correct 790 ms 77504 KB Output is correct
42 Correct 776 ms 77008 KB Output is correct
43 Correct 917 ms 84812 KB Output is correct
44 Correct 703 ms 78188 KB Output is correct
45 Correct 737 ms 80488 KB Output is correct
46 Correct 748 ms 79592 KB Output is correct
47 Correct 709 ms 87356 KB Output is correct
48 Correct 650 ms 87256 KB Output is correct
49 Correct 661 ms 87480 KB Output is correct
50 Correct 663 ms 87224 KB Output is correct
51 Correct 836 ms 86068 KB Output is correct
52 Correct 835 ms 86084 KB Output is correct