oj.uz

Submission #434355

# Submission time Handle Problem Language Result Execution time Memory
434355 2021-06-21T03:23:20 Z cuom1999 Werewolf (IOI18_werewolf) C++14
100 / 100
 2926 ms 190316 KB 
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> lab;
    DSU(int n) {
        lab.assign(n + 1, -1);
    }

    int merge(int a, int b) {
        if (lab[a] > lab[b]) {
            swap(a, b);
        }
        lab[a] += lab[b];
        lab[b] = a;
        return a;
    }

    int getRoot(int a) {
        while (lab[a] >= 0) a = lab[a];
        return a;
    }
};

struct DSUTree {
    struct Node {
        int tin, tout, weight;
        vector<int> child;
    };

    int n, TIME = 0;
    vector<array<int, 3>> edges;
    vector<int> root, eulerTour;
    vector<vector<int>> par;
    vector<Node> nodes;
    
    DSUTree(int n): n(n) {
        root.resize(n + 1);
        nodes.resize(2 * n);
        par.assign(2 * n, vector<int>(20));
    }

    void addEdge(int u, int v, int c) {
        edges.push_back({c, u, v});
    }

    void construct() {
        sort(edges.begin(), edges.end());
        DSU dsu(n);

        for (int i = 1; i <= n; i++) {
            root[i] = i;
            nodes[i].weight = -1e9;
        }

        int cnt = n;
        for (auto e: edges) {
            int a = dsu.getRoot(e[1]);
            int b = dsu.getRoot(e[2]);
            if (a == b) continue;

            int root1 = root[a], root2 = root[b];
            a = dsu.merge(a, b);
            root[a] = ++cnt;
            nodes[cnt].child.push_back(root1);
            nodes[cnt].child.push_back(root2);
            nodes[cnt].weight = e[0];

            par[root1][0] = cnt;
            par[root2][0] = cnt;
        }

        dfs(2 * n - 1);
        getOrder();

        for (int i = 1; i < 20; i++) {
            for (int j = 1; j <= 2 * n - 1; j++) {
                par[j][i] = par[par[j][i - 1]][i - 1];
            }
        }
    }

    void dfs(int u) {
        nodes[u].tin = ++TIME;
        eulerTour.push_back(u);
        for (auto i: nodes[u].child) {
            dfs(i);
        }
        nodes[u].tout = ++TIME;
        eulerTour.push_back(u);
    }

    vector<int> order;
    void getOrder() {
        vector<int> vs(2 * n + 1);
        for (auto i: eulerTour) {
            if (i <= n && vs[i] == 0) {
                order.push_back(i);
            }
            vs[i] = 1;
        }
    }

    // return the interval that s can reach through edges <= r
    pair<int, int> getInterval(int s, int r) {
        // find farthest parent has weight <= r
        for (int i = 19; i >= 0; i--) {
            int p = par[s][i];
            if (p && nodes[p].weight <= r) {
                s = p;
            }
        }

        // find [l, r] such that tin[s] <= tin[i] <= tout[s]
        int lower = 0, upper = n - 1;
        while (lower < upper) {
            int mid = (lower + upper) / 2;
            if (nodes[s].tin <= nodes[order[mid]].tin) {
                upper = mid;
            }
            else {
                lower = mid + 1;
            }
        }

        int l = lower;

        lower = 0, upper = n - 1;
        while (lower < upper) {
            int mid = (lower + upper + 1) / 2;
            if (nodes[s].tout >= nodes[order[mid]].tin) {
                lower = mid;
            }
            else {
                upper = mid - 1;
            }
        }

        return {l, lower};
    }
};

struct BIT {
    int n;
    vector<int> fen;
    BIT(int n): n(n) {
        fen.resize(n + 1);
    }

    void add(int u, int v) {
        for (int i = u; i <= n; i += i & -i) {
            fen[i] += v;
        }
    }

    int getSum(int u) {
        int res = 0;
        for (int i = u; i; i -= i & -i) {
            res += fen[i];
        }
        return res;
    }
};

std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int m = x.size(), q = S.size();
    DSUTree maxTree(n), minTree(n);
    for (int i = 1; i <= m; i++) {
        int u = x[i - 1], v = y[i - 1];
        u++; v++;
        maxTree.addEdge(u, v, -min(u, v)); // >= l
        minTree.addEdge(u, v, max(u, v)); // <= r
    }

    minTree.construct();
    maxTree.construct();

    vector<int> a = minTree.order;
    vector<int> b = maxTree.order;
    vector<int> pos(n + 1), c(n + 1);

    // for (auto i: a) cout << i << " ";
    // cout << endl;
    // for (auto i: b) cout << i << " ";
    // cout << endl;

    for (int i = 0; i < n; i++) {
        pos[a[i]] = i + 1;
    }
    for (int i = 0; i < n; i++) {
        c[i + 1] = pos[b[i]];
    }

    vector<int> ret;
    vector<int> calc(q);
    vector<vector<array<int, 4>>> query(n + 1);
    for (int i = 0; i < q; i++) {
        int s = S[i], e = E[i], l = L[i], r = R[i];
        // cin >> s >> e >> l >> r;
        s++; e++; l++; r++;
        auto [l1, r1] = minTree.getInterval(e, r);
        auto [l2, r2] = maxTree.getInterval(s, -l);

        l1++; r1++; l2++; r2++;
        query[l2 - 1].push_back({l1, r1, i, 0});
        query[r2].push_back({l1, r1, i, 1});
    }

    BIT bit(n);
    for (int i = 0; i <= n; i++) {
        if (i) bit.add(c[i], 1);
        for (auto q: query[i]) {
            int val = bit.getSum(q[1]) - bit.getSum(q[0] - 1);
            if (q[3] == 0) {
                calc[q[2]] -= val;
            }
            else {
                calc[q[2]] += val;
            }
        }
    }

    for (int i = 0; i < q; i++) {
        if (calc[i]) {
            ret.push_back(1);
        }
        else {
            ret.push_back(0);
        }
    }

    return ret;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:203:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  203 |         auto [l1, r1] = minTree.getInterval(e, r);
      |              ^
werewolf.cpp:204:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  204 |         auto [l2, r2] = maxTree.getInterval(s, -l);
      |              ^

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 1 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 1 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 12 ms 3124 KB Output is correct
11 Correct 12 ms 3020 KB Output is correct
12 Correct 11 ms 3020 KB Output is correct
13 Correct 12 ms 3164 KB Output is correct
14 Correct 11 ms 3148 KB Output is correct
15 Correct 12 ms 3184 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2175 ms 182440 KB Output is correct
2 Correct 2563 ms 185032 KB Output is correct
3 Correct 2118 ms 182696 KB Output is correct
4 Correct 1750 ms 180972 KB Output is correct
5 Correct 1802 ms 181028 KB Output is correct
6 Correct 2086 ms 182412 KB Output is correct
7 Correct 1526 ms 181192 KB Output is correct
8 Correct 2508 ms 184892 KB Output is correct
9 Correct 1511 ms 181428 KB Output is correct
10 Correct 1045 ms 180960 KB Output is correct
11 Correct 1140 ms 180824 KB Output is correct
12 Correct 1230 ms 180300 KB Output is correct
13 Correct 2772 ms 185296 KB Output is correct
14 Correct 2805 ms 185376 KB Output is correct
15 Correct 2867 ms 185192 KB Output is correct
16 Correct 2833 ms 185292 KB Output is correct
17 Correct 1462 ms 181168 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 1 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 12 ms 3124 KB Output is correct
11 Correct 12 ms 3020 KB Output is correct
12 Correct 11 ms 3020 KB Output is correct
13 Correct 12 ms 3164 KB Output is correct
14 Correct 11 ms 3148 KB Output is correct
15 Correct 12 ms 3184 KB Output is correct
16 Correct 2175 ms 182440 KB Output is correct
17 Correct 2563 ms 185032 KB Output is correct
18 Correct 2118 ms 182696 KB Output is correct
19 Correct 1750 ms 180972 KB Output is correct
20 Correct 1802 ms 181028 KB Output is correct
21 Correct 2086 ms 182412 KB Output is correct
22 Correct 1526 ms 181192 KB Output is correct
23 Correct 2508 ms 184892 KB Output is correct
24 Correct 1511 ms 181428 KB Output is correct
25 Correct 1045 ms 180960 KB Output is correct
26 Correct 1140 ms 180824 KB Output is correct
27 Correct 1230 ms 180300 KB Output is correct
28 Correct 2772 ms 185296 KB Output is correct
29 Correct 2805 ms 185376 KB Output is correct
30 Correct 2867 ms 185192 KB Output is correct
31 Correct 2833 ms 185292 KB Output is correct
32 Correct 1462 ms 181168 KB Output is correct
33 Correct 2782 ms 183268 KB Output is correct
34 Correct 554 ms 34188 KB Output is correct
35 Correct 2926 ms 185604 KB Output is correct
36 Correct 2456 ms 183072 KB Output is correct
37 Correct 2919 ms 184856 KB Output is correct
38 Correct 2616 ms 183516 KB Output is correct
39 Correct 2533 ms 188276 KB Output is correct
40 Correct 2001 ms 190124 KB Output is correct
41 Correct 2019 ms 183172 KB Output is correct
42 Correct 1191 ms 182000 KB Output is correct
43 Correct 2838 ms 189916 KB Output is correct
44 Correct 2683 ms 184620 KB Output is correct
45 Correct 1717 ms 187300 KB Output is correct
46 Correct 1977 ms 187416 KB Output is correct
47 Correct 2869 ms 185524 KB Output is correct
48 Correct 2915 ms 185228 KB Output is correct
49 Correct 2886 ms 185452 KB Output is correct
50 Correct 2868 ms 185376 KB Output is correct
51 Correct 1667 ms 190280 KB Output is correct
52 Correct 1682 ms 190316 KB Output is correct