Submission #1255855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255855		biank	Werewolf (IOI18_werewolf)	C++20	100 / 100	467 ms	137760 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

struct DSU {
    vi par;
    vector<vi> adj;
    DSU(int n) : par(n), adj(n) {
        iota(all(par), 0);
    }
    int find(int x) {
        if (par[x] == x) return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        int p = sz(par);
        par[x] = p, par[y] = p;
        par.pb(p);
        adj.eb();
        adj.back().pb(x);
        adj.back().pb(y);
    }
};

void dfs(int u, vector<vi> &adj, vi &low, vi &high, int &t) {
    low[u] = t++;
    for (int v : adj[u]) {
        dfs(v, adj, low, high, t);
    }
    high[u] = t;
}

struct FTree {
    int n;
    vi ft;
    FTree(int _n) : n(_n + 9), ft(n, 0) {}
    void update(int p) {
        for (++p; p < n; p += p & -p) ft[p]++;
    }
    int get(int p) {
        int s = 0;
        for (; p > 0; p -= p & -p) s += ft[p];
        return s;
    }
    int query(int l, int r) {
        return get(r) - get(l);
    }
};

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int M = sz(X), Q = sz(S);
    vector<vi> edgesByMin(N), edgesByMax(N);
    forn(i, M) edgesByMin[min(X[i], Y[i])].pb(i);
    forn(i, M) edgesByMax[max(X[i], Y[i])].pb(i);
    vector<vi> queriesByL(N), queriesByR(N);
    forn(i, Q) queriesByL[L[i]].pb(i);
    forn(i, Q) queriesByR[R[i]].pb(i);
    DSU left(N), right(N);
    vi parentL(Q), parentR(Q);
    dforn(l, N) {
        for (int i : edgesByMin[l]) {
            left.unite(X[i], Y[i]);
        }
        for (int i : queriesByL[l]) {
            parentL[i] = left.find(S[i]);
        }
    }
    forn(r, N) {
        for (int i : edgesByMax[r]) {
            right.unite(X[i], Y[i]);
        }
        for (int i : queriesByR[r]) {
            parentR[i] = right.find(E[i]);
        }
    }
    vi lowL(2 * N - 1), highL(2 * N - 1);
    vi lowR(2 * N - 1), highR(2 * N - 1);
    int tL = 0, tR = 0;
    dfs(left.find(0), left.adj, lowL, highL, tL);
    dfs(right.find(0), right.adj, lowR, highR, tR);
    vector<vi> toAdd(2 * N);
    forn(i, N) toAdd[lowL[i]].pb(lowR[i]);
    vector<vector<pair<ii, int>>> queries(2 * N);
    forn(i, Q) {
        ii range = {lowR[parentR[i]], highR[parentR[i]]};
        queries[lowL[parentL[i]]].eb(range, -i - 1);
        queries[highL[parentL[i]]].eb(range, i + 1);
    }
    FTree ft(2 * N);
    vi ret(Q, 0);
    forn(curr, 2 * N) {
        for (auto [range, data] : queries[curr]) {
            int type = data < 0 ? -1 : 1;
            int id = abs(data) - 1;
            auto [l, r] = range;
            ret[id] += type * ft.query(l, r);
        }
        for (int i : toAdd[curr]) ft.update(i);
    }
    forn(i, Q) {
        assert(ret[i] >= 0);
        if (ret[i] > 0) ret[i] = 1;
    }
    return ret;
}

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