oj.uz

Submission #688596

# Submission time Handle Problem Language Result Execution time Memory
688596 2023-01-27T19:52:44 Z bebra Werewolf (IOI18_werewolf) C++17
100 / 100
 2217 ms 97796 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;

struct DSU {
    vector<int> parent;
    vector<vector<int>> tree;
    vector<vector<int>> binup;
    vector<int> tin;
    vector<int> tout;
    vector<int> vertices;
    int n;
    int max_k;
    int timer;

    DSU(int _n) : n(_n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);

        tree.resize(n);
        tin.resize(n);
        tout.resize(n);
        vertices.resize(n);
        
        timer = 0;
        max_k = __lg(n) + 2;
        binup.assign(max_k, vector<int>(n));
    }
    
    int find(int v) {
        if (parent[v] == v) {
            return v;
        } else {
            return parent[v] = find(parent[v]);
        }
    }

    void unite(int u, int v) {
        u = find(u);
        assert(parent[v] == v);
        if (u == v) return;
        tree[v].push_back(u);
        parent[u] = v;
    }

    void dfs(int v) {
        vertices[timer] = v;
        tin[v] = timer++;
        for (auto u : tree[v]) {
            binup[0][u] = v;
            for (int k = 1; k < max_k; ++k) {
                binup[k][u] = binup[k - 1][binup[k - 1][u]];
            }
            dfs(u);
        }
        tout[v] = timer - 1;
    }

    void traverse() {
        for (int v = 0; v < n; ++v) {
            if (parent[v] == v) {
                for (int k = 0; k < max_k; ++k) {
                    binup[k][v] = v;
                }
                dfs(v);
            }
        }
    }
};


struct Query {
    static const int BLOCK_SIZE = 450;

    int l;
    int r;
    int idx;
    int block;

    Query(int _l = 0, int _r = 0, int _idx = 0) : l(_l), r(_r), idx(_idx) {
        block = l / BLOCK_SIZE;
    }

    bool operator<(const Query& other) const {
        return tie(block, r) < tie(other.block, other.r);
    }
};


struct FenwickTree {
    vector<int> tree;
    int n;

    FenwickTree(int _n) : n(_n) {
        tree.resize(n);
    }

    void update(int pos, int value) {
        for (int i = pos; i < n; i |= i + 1) {
            tree[i] += value;
        }
    }

    int query(int l, int r) {
        int res = 0;
        for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
            res += tree[i];
        }
        for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) {
            res -= tree[i];
        }
        return res;
    }
};



vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> f, vector<int> ls, vector<int> rs) {
    vector<vector<int>> g(n);
    int m = x.size();
    for (int i = 0; i < m; ++i) {
        int u = x[i];
        int v = y[i];
        g[u].push_back(v);
        g[v].push_back(u);
    }
    DSU dsu_right(n);
    for (int v = 0; v < n; ++v) {
        for (auto u : g[v]) {
            if (u > v) continue;
            dsu_right.unite(u, v);
        }
    }
    DSU dsu_left(n);
    for (int v = n - 1; v >= 0; --v) {
        for (auto u : g[v]) {
            if (u < v) continue;
            dsu_left.unite(u, v);
        }
    }
    dsu_right.traverse();
    dsu_left.traverse();

    int q = s.size();
    vector<int> ans(q);
    vector<Query> queries(q);
    for (int i = 0; i < q; ++i) {
        int v = f[i];
        for (int k = dsu_right.max_k - 1; k >= 0; --k) {
            if (dsu_right.binup[k][v] < rs[i]) {
                v = dsu_right.binup[k][v];
            }
        }
        if (dsu_right.binup[0][v] <= rs[i]) v = dsu_right.binup[0][v];

        queries[i] = Query(dsu_right.tin[v], dsu_right.tout[v], i);
    }
    sort(queries.begin(), queries.end());


    FenwickTree fenwick(n);
    auto move_borders = [&](int& curr_l, int& curr_r, int l, int r) {
        while (curr_l > l) {
            --curr_l;
            int v = dsu_right.vertices[curr_l];
            fenwick.update(dsu_left.tin[v], 1);
        }
        while (curr_r < r) {
            ++curr_r;
            int v = dsu_right.vertices[curr_r];
            fenwick.update(dsu_left.tin[v], 1);
        }
        while (curr_l < l) {
            int v = dsu_right.vertices[curr_l];
            fenwick.update(dsu_left.tin[v], -1);
            ++curr_l;
        }
        while (curr_r > r) {
            int v = dsu_right.vertices[curr_r];
            fenwick.update(dsu_left.tin[v], -1);
            --curr_r;
        }
    };

    int curr_l = 0;
    int curr_r = -1;
    for (const auto& [l, r, idx, block] : queries) {
        move_borders(curr_l, curr_r, l, r);
        int v = s[idx];
        for (int k = dsu_left.max_k - 1; k >= 0; --k) {
            if (dsu_left.binup[k][v] > ls[idx]) {
                v = dsu_left.binup[k][v];
            }
        }
        if (dsu_left.binup[0][v] >= ls[idx]) v = dsu_left.binup[0][v];

        if (fenwick.query(dsu_left.tin[v], dsu_left.tout[v]) > 0) {
            ans[idx] = 1;
        }
    }

    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 8 ms 1492 KB Output is correct
11 Correct 5 ms 1364 KB Output is correct
12 Correct 5 ms 1364 KB Output is correct
13 Correct 11 ms 1492 KB Output is correct
14 Correct 11 ms 1460 KB Output is correct
15 Correct 6 ms 1588 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 87608 KB Output is correct
2 Correct 699 ms 89948 KB Output is correct
3 Correct 1129 ms 88384 KB Output is correct
4 Correct 1613 ms 87740 KB Output is correct
5 Correct 1583 ms 87696 KB Output is correct
6 Correct 1444 ms 87656 KB Output is correct
7 Correct 585 ms 87524 KB Output is correct
8 Correct 566 ms 89888 KB Output is correct
9 Correct 415 ms 88428 KB Output is correct
10 Correct 444 ms 87712 KB Output is correct
11 Correct 511 ms 87692 KB Output is correct
12 Correct 523 ms 87656 KB Output is correct
13 Correct 1051 ms 94948 KB Output is correct
14 Correct 1058 ms 94956 KB Output is correct
15 Correct 1024 ms 94900 KB Output is correct
16 Correct 1028 ms 94908 KB Output is correct
17 Correct 609 ms 87656 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 8 ms 1492 KB Output is correct
11 Correct 5 ms 1364 KB Output is correct
12 Correct 5 ms 1364 KB Output is correct
13 Correct 11 ms 1492 KB Output is correct
14 Correct 11 ms 1460 KB Output is correct
15 Correct 6 ms 1588 KB Output is correct
16 Correct 704 ms 87608 KB Output is correct
17 Correct 699 ms 89948 KB Output is correct
18 Correct 1129 ms 88384 KB Output is correct
19 Correct 1613 ms 87740 KB Output is correct
20 Correct 1583 ms 87696 KB Output is correct
21 Correct 1444 ms 87656 KB Output is correct
22 Correct 585 ms 87524 KB Output is correct
23 Correct 566 ms 89888 KB Output is correct
24 Correct 415 ms 88428 KB Output is correct
25 Correct 444 ms 87712 KB Output is correct
26 Correct 511 ms 87692 KB Output is correct
27 Correct 523 ms 87656 KB Output is correct
28 Correct 1051 ms 94948 KB Output is correct
29 Correct 1058 ms 94956 KB Output is correct
30 Correct 1024 ms 94900 KB Output is correct
31 Correct 1028 ms 94908 KB Output is correct
32 Correct 609 ms 87656 KB Output is correct
33 Correct 1505 ms 87828 KB Output is correct
34 Correct 505 ms 35012 KB Output is correct
35 Correct 2217 ms 89956 KB Output is correct
36 Correct 1857 ms 88168 KB Output is correct
37 Correct 2147 ms 89212 KB Output is correct
38 Correct 2021 ms 88624 KB Output is correct
39 Correct 1170 ms 95268 KB Output is correct
40 Correct 1179 ms 97796 KB Output is correct
41 Correct 504 ms 88636 KB Output is correct
42 Correct 539 ms 88188 KB Output is correct
43 Correct 700 ms 94712 KB Output is correct
44 Correct 1128 ms 89192 KB Output is correct
45 Correct 1060 ms 95556 KB Output is correct
46 Correct 1069 ms 95288 KB Output is correct
47 Correct 1039 ms 95108 KB Output is correct
48 Correct 1052 ms 94916 KB Output is correct
49 Correct 1043 ms 95172 KB Output is correct
50 Correct 1049 ms 95036 KB Output is correct
51 Correct 600 ms 97552 KB Output is correct
52 Correct 632 ms 97596 KB Output is correct