Submission #688596

#	Time	Username	Problem	Language	Result	Execution time	Memory
688596		bebra	Werewolf (IOI18_werewolf)	C++17	100 / 100	2217 ms	97796 KiB

werewolf

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