Submission #434355

#	Time	Username	Problem	Language	Result	Execution time	Memory
434355		cuom1999	Werewolf (IOI18_werewolf)	C++14	100 / 100	2926 ms	190316 KiB

werewolf

#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 (stderr)

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51