Submission #377944

#	Time	Username	Problem	Language	Result	Execution time	Memory
377944		smax	Werewolf (IOI18_werewolf)	C++17	100 / 100	890 ms	115416 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int ti, comp;
    vector<int> par, in, out, order;
    vector<vector<int>> adj;

    DSU(int n) : ti(0), comp(n), par(n), in(n), out(n), order({n}), adj(n) {
        iota(par.begin(), par.end(), 0);
    }

    int find(int u) {
        return u == par[u] ? u : par[u] = find(par[u]);
    }

    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return;
        comp--;
        par.push_back((int) par.size());
        par[u] = par[v] = (int) par.size() - 1;
        in.emplace_back();
        out.emplace_back();
        adj.push_back({u, v});
    }

    void dfs(int u) {
        in[u] = ++ti;
        order.push_back(u);
        for (int v : adj[u])
            dfs(v);
        out[u] = ti;
    }
};

template<typename T>
struct BIT {
    int n;
    vector<T> bit;

    BIT(int _n) : n(_n), bit(n + 1) {}

    T query(int i) {
        T ret = 0;
        for (; i>0; i-=i&-i)
            ret += bit[i];
        return ret;
    }

    T query(int l, int r) {
        return query(r) - query(l-1);
    }

    void update(int i, T val) {
        for (; i<=n; i+=i&-i)
            bit[i] += val;
    }
};

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 = (int) X.size(), q = (int) S.size();
    vector<vector<int>> adj(N);
    for (int i=0; i<m; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    vector<vector<int>> queryL(N), queryR(N);
    for (int i=0; i<q; i++) {
        queryL[L[i]].push_back(i);
        queryR[R[i]].push_back(i);
    }

    DSU inc(N), dec(N);
    for (int u=0; u<N; u++) {
        for (int v : adj[u])
            if (v < u)
                inc.unite(u, v);
        for (int i : queryR[u])
            E[i] = inc.find(E[i]);
    }
    for (int u=N-1; u>=0; u--) {
        for (int v : adj[u])
            if (v > u)
                dec.unite(u, v);
        for (int i : queryL[u])
            S[i] = dec.find(S[i]);
    }
    inc.dfs(inc.find(0));
    dec.dfs(dec.find(0));

    int o1 = (int) inc.order.size(), o2 = (int) dec.order.size();
    vector<vector<pair<int, int>>> pts(o1);
    BIT<int> bit(o2);
    vector<int> ret(q);
    for (int i=0; i<q; i++) {
        pts[inc.in[E[i]] - 1].emplace_back(i, -1);
        pts[inc.out[E[i]]].emplace_back(i, 1);
    }
    for (int i=0; i<o1; i++) {
        if (inc.order[i] < N)
            bit.update(dec.in[inc.order[i]], 1);
        for (auto [j, c] : pts[i])
            ret[j] += bit.query(dec.in[S[j]], dec.out[S[j]]) * c;
    }

    for (int i=0; i<q; i++)
        ret[i] = ret[i] > 0;
    return ret;
}

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