Submission #666156

#	Time	Username	Problem	Language	Result	Execution time	Memory
666156		amsraman	Werewolf (IOI18_werewolf)	C++14	100 / 100	546 ms	75616 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

template <typename T>
struct FenwickTree {
    int n;
    vector<T> bit;
    FenwickTree(int n): n(n), bit(n, 0) {};
    FenwickTree(vector<T> & init): n((int) init.size()), bit((int) init.size()) {
        copy(init.begin(), init.end(), bit.begin());
        for(int i = 1; i <= n; i++) {
            if(i + (i & -i) <= n) {
                bit[i + (i & -i) - 1] += bit[i - 1];
            }
        }
    }
    T qry(int k) {
        T ret = 0;
        for(k++; k > 0; k -= k & -k) {
            ret += bit[k - 1];
        }
        return ret;
    }
    T qry(int l, int r) {
        return qry(r) - qry(l - 1);
    }
    void upd(int k, T x) {
        for(k++; k <= n; k += k & -k) {
            bit[k - 1] += x;
        }
    }
};

vector<int> link, sz, tour1, tour2;
vector<vector<int>> dsu_graph;

int find(int x) {
    return (x == link[x] ? x : link[x] = find(link[x]));
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    if(sz[x] < sz[y]) swap(x, y);
    link[y] = x, sz[x] += sz[y], dsu_graph[x].push_back(y);
}

void dfs(int u) {
    tour1.push_back(u);
    for(int v: dsu_graph[u]) {
        dfs(v);
    }
}

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
    int m = x.size(), q = s.size();
    link.resize(n);
    vector<int> pos1(n), pos2(n), num(q, 0), ans(q);
    vector<pair<int, int>> were(q), wolf(q);
    vector<vector<int>> g(n), rem(n), pts(n), add(n);
    FenwickTree<int> ft(n);
    for(int i = 0; i < m; i++) {
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }
    auto proc = [&](int start, int end, int step) { // wolf then were
        iota(link.begin(), link.end(), 0), sz.resize(n, 1), dsu_graph.resize(n);
        swap(tour1, tour2), swap(were, wolf);
        vector<vector<int>> handle(n);
        for(int i = 0; i < q; i++) {
            swap(s[i], e[i]), swap(l[i], r[i]);
            handle[l[i]].push_back(i);
        }
        for(int i = start; i != end; i += step) {
            for(int j: g[i]) {
                if(step * j < step * i) {
                    unite(i, j);
                }
            }
            for(int ind: handle[i]) {
                were[ind] = {find(s[ind]), sz[find(s[ind])]};
            }
        }
        dfs(find(0));
        sz.clear(), dsu_graph.clear();
    };
    proc(0, n, 1), proc(n - 1, -1, -1);
    for(int i = 0; i < n; i++) {
        pos1[tour1[i]] = i, pos2[tour2[i]] = i;
    }
    for(int i = 0; i < n; i++) {
        pts[pos1[tour2[i]]].push_back(i);
    }
    for(int i = 0; i < q; i++) {
        were[i] = {pos1[were[i].first], pos1[were[i].first] + were[i].second - 1};
        wolf[i] = {pos2[wolf[i].first], pos2[wolf[i].first] + wolf[i].second - 1};
        rem[were[i].first].push_back(i), add[were[i].second].push_back(i);
    }
    for(int i = 0; i < n; i++) {
        for(int ind: rem[i]) {
            num[ind] -= ft.qry(wolf[ind].first, wolf[ind].second);
        }
        for(int p: pts[i]) {
            ft.upd(p, 1);
        }
        for(int ind: add[i]) {
            num[ind] += ft.qry(wolf[ind].first, wolf[ind].second);
        }
    }
    for(int i = 0; i < q; i++) {
        ans[i] = num[i] > 0;
    }
    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51