oj.uz

Submission #970630

# Submission time Handle Problem Language Result Execution time Memory
970630 2024-04-26T23:12:36 Z BestCrazyNoob Werewolf (IOI18_werewolf) C++17
100 / 100
 589 ms 130352 KB 
#include "werewolf.h"
#include <vector>
#include <utility>
#include <array>

using namespace std;
constexpr int INF = 1e9;
constexpr int H = 20;

struct DSU {
    // O(a_inv(m, n))
    vector<int> rs;
    DSU(int n) {
        rs.resize(n, -1);
    }
    int repr(int a) {
        return rs[a] < 0 ? a : (rs[a] = repr(rs[a]));
    }
    bool join(int a, int b) {
        a = repr(a);
        b = repr(b);
        if (a == b) return false;
        // enforce size(a) > size(b)
        if (-a < -b) swap(a, b);
        rs[a] += rs[b];
        rs[b] = a;
        return true;
    }
};

struct DSU2 {
    // O(log(n))
    vector<int> rs;
    DSU2(int n) {
        rs.resize(n, -1);
    }
    int repr(int a) {
        return rs[a] < 0 ? a : (rs[a] = repr(rs[a]));
    }
    // a will become the repr
    int join(int a, int b) {
        a = repr(a);
        b = repr(b);
        // use given order
        rs[a] += rs[b];
        rs[b] = a;
        return b; // after call to repr()
    }
};

struct SegTree {
    vector<int> tree;
    int sz;
    int ql, qr;
    SegTree() {}
    SegTree(int n) {
        sz = 1;
        while (sz < n) sz *= 2;
        tree.resize(2*sz, -1);
    }
    int __query(int ni, int nl, int nr) {
        if (qr <= nl || nr <= ql) return -1;
        if (ql <= nl && nr <= qr) return tree[ni];
        int nm = (nl+nr)/2;
        return max(__query(2*ni, nl, nm), __query(2*ni+1, nm, nr));
    }
    int query(int l, int r) {
        ql = l;
        qr = r;
        return __query(1, 0, sz);
    }
    void set(int i, int x) {
        i += sz;
        tree[i] = x;
        while (i > 1) {
            i /= 2;
            tree[i] = max(tree[2*i], tree[2*i+1]);
        }
    }
};

vector<vector<int>> graph, adj0, adj1;
vector<int> tin0, tin1, tout0, tout1, ans;
int N, M, curr_eul;
SegTree seg;
vector<array<int, H>> anc0, anc1;
// other, q_index
vector<vector<pair<int, int>>> queries;

void setup0() {
    DSU dsu(N);
    DSU2 maxel(N);
    adj0.resize(N);
    for (int i = 0; i < N; ++i) {
        for (int x: graph[i]) {
            if (x > i || !dsu.join(i, x)) continue;
            const int other = maxel.join(i, x);
            adj0[i].push_back(other);
            adj0[other].push_back(i);
        }
    }
}

void setup1() {
    DSU dsu(N);
    DSU2 maxel(N);
    adj1.resize(N);
    for (int i = N-1; i >= 0; --i) {
        for (int x: graph[i]) {
            if (x < i || !dsu.join(i, x)) continue;
            const int other = maxel.join(i, x);
            adj1[i].push_back(other);
            adj1[other].push_back(i);
        }
    }
}

void euler(int curr, int prev, vector<vector<int>> &adj, vector<int> &tin, vector<int> &tout, vector<array<int, H>> &anc) {
    tin[curr] = curr_eul++;
    for (int x: adj[curr]) {
        if (x == prev) continue;
        anc[x][0] = curr;
        euler(x, curr, adj, tin, tout, anc);
    }
    tout[curr] = curr_eul;
}

void calc_anc(vector<array<int, H>> &anc) {
    for (int h = 0; h < H-1; ++h) {
        for (auto &arr: anc) {
            arr[h+1] = arr[h] == -1 ? -1 : anc[arr[h]][h];
        }
    }
}

int get_anc0(int x, int d) {
    for (int h = H-1; h >= 0; --h) {
        if (anc0[x][h] != -1 && anc0[x][h] <= d) x = anc0[x][h];
    }
    return x;
}

int get_anc1(int x, int d) {
    for (int h = H-1; h >= 0; --h) {
        if (anc1[x][h] != -1 && anc1[x][h] >= d) x = anc1[x][h];
    }
    return x;
}

void answer(int curr, int prev) {
    for (int x: adj0[curr]) {
        if (x == prev) continue;
        answer(x, curr);
    }
    // mark the current node visited and say when it was visited
    seg.set(tin1[curr], tin0[curr]);
    for (auto [other, q_index]: queries[curr]) {
        ans[q_index] = seg.query(tin1[other], tout1[other]) >= tin0[curr];
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    const int Q = S.size();
    M = X.size();
    ::N = N;

    graph.resize(N);
    for (int m = 0; m < M; ++m) {
        graph[X[m]].push_back(Y[m]);
        graph[Y[m]].push_back(X[m]);
    }
    // trasform into tree
    setup0();
    setup1();

    anc0.resize(N);
    tin0.resize(N);
    tout0.resize(N);
    anc0[N-1][0] = -1;
    curr_eul = 0;
    euler(N-1, -1, adj0, tin0, tout0, anc0);
    calc_anc(anc0);

    anc1.resize(N);
    tin1.resize(N);
    tout1.resize(N);
    anc1[0][0] = -1;
    curr_eul = 0;
    euler(0, -1, adj1, tin1, tout1, anc1);
    calc_anc(anc1);
    
    ans.resize(Q);
    queries.resize(N);
    for (int q = 0; q < Q; ++q) {
        queries[get_anc0(E[q], R[q])].push_back({get_anc1(S[q], L[q]), q});
    }

    seg = SegTree(N);
    answer(N-1, -1);

    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 5 ms 1884 KB Output is correct
11 Correct 5 ms 1884 KB Output is correct
12 Correct 4 ms 1628 KB Output is correct
13 Correct 5 ms 2140 KB Output is correct
14 Correct 5 ms 2340 KB Output is correct
15 Correct 5 ms 1884 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 89076 KB Output is correct
2 Correct 433 ms 108084 KB Output is correct
3 Correct 417 ms 100220 KB Output is correct
4 Correct 436 ms 96992 KB Output is correct
5 Correct 405 ms 96816 KB Output is correct
6 Correct 456 ms 96984 KB Output is correct
7 Correct 530 ms 96276 KB Output is correct
8 Correct 406 ms 108156 KB Output is correct
9 Correct 356 ms 100188 KB Output is correct
10 Correct 405 ms 96624 KB Output is correct
11 Correct 357 ms 97032 KB Output is correct
12 Correct 384 ms 96416 KB Output is correct
13 Correct 544 ms 113212 KB Output is correct
14 Correct 514 ms 113308 KB Output is correct
15 Correct 509 ms 113116 KB Output is correct
16 Correct 550 ms 112944 KB Output is correct
17 Correct 450 ms 96524 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 5 ms 1884 KB Output is correct
11 Correct 5 ms 1884 KB Output is correct
12 Correct 4 ms 1628 KB Output is correct
13 Correct 5 ms 2140 KB Output is correct
14 Correct 5 ms 2340 KB Output is correct
15 Correct 5 ms 1884 KB Output is correct
16 Correct 559 ms 89076 KB Output is correct
17 Correct 433 ms 108084 KB Output is correct
18 Correct 417 ms 100220 KB Output is correct
19 Correct 436 ms 96992 KB Output is correct
20 Correct 405 ms 96816 KB Output is correct
21 Correct 456 ms 96984 KB Output is correct
22 Correct 530 ms 96276 KB Output is correct
23 Correct 406 ms 108156 KB Output is correct
24 Correct 356 ms 100188 KB Output is correct
25 Correct 405 ms 96624 KB Output is correct
26 Correct 357 ms 97032 KB Output is correct
27 Correct 384 ms 96416 KB Output is correct
28 Correct 544 ms 113212 KB Output is correct
29 Correct 514 ms 113308 KB Output is correct
30 Correct 509 ms 113116 KB Output is correct
31 Correct 550 ms 112944 KB Output is correct
32 Correct 450 ms 96524 KB Output is correct
33 Correct 589 ms 100716 KB Output is correct
34 Correct 191 ms 35240 KB Output is correct
35 Correct 537 ms 107852 KB Output is correct
36 Correct 559 ms 99276 KB Output is correct
37 Correct 563 ms 106028 KB Output is correct
38 Correct 544 ms 100664 KB Output is correct
39 Correct 482 ms 129328 KB Output is correct
40 Correct 555 ms 110452 KB Output is correct
41 Correct 450 ms 103292 KB Output is correct
42 Correct 461 ms 98100 KB Output is correct
43 Correct 514 ms 114484 KB Output is correct
44 Correct 471 ms 104892 KB Output is correct
45 Correct 453 ms 130352 KB Output is correct
46 Correct 457 ms 129840 KB Output is correct
47 Correct 567 ms 113508 KB Output is correct
48 Correct 522 ms 113128 KB Output is correct
49 Correct 498 ms 113208 KB Output is correct
50 Correct 482 ms 112944 KB Output is correct
51 Correct 521 ms 111156 KB Output is correct
52 Correct 507 ms 111168 KB Output is correct