Submission #890156

#	Time	Username	Problem	Language	Result	Execution time	Memory
890156		winter0101	Werewolf (IOI18_werewolf)	C++14	100 / 100	541 ms	116640 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn = 2e5 + 9;
struct DSU_Tree {
    vector<vector<int>>a;
    vector<int>f;
    int n;
    int fs(int u) {
        if (f[u] < 0)
            return u;

        return f[u] = fs(f[u]);
    }
    void unite(int u, int v) {
        u = fs(u), v = fs(v);

        if (u == v)
            return;

        n++;
        f[n] = f[u] + f[v];
        a[n].pb(u);
        a[n].pb(v);
        f[u] = n;
        f[v] = n;
    }
    int tme = 0;
    vector<int>in, out, rev;
    void dfs(int u) {
        in[u] = ++tme;
        rev[in[u]] = u;

        for (auto v : a[u]) {
            dfs(v);
        }

        out[u] = tme;
    }
    void resz(int _n) {
        n = _n;
        f.resize(2 * n + 9);
        a.resize(2 * n + 9);
        for1(i, 1, n)f[i] = -1;
        in.resize(2 * n + 9);
        out.resize(2 * n + 9);
        rev.resize(2 * n + 9);
    }
};
int st[maxn * 8];
void update(int id, int l, int r, int u, int val) {
    if (l > u || r < u)
        return;

    if (l == r) {
        st[id] = val;
        return;
    }

    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, val);
    update(id * 2 + 1, mid + 1, r, u, val);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get(int id, int l, int r, int u, int v) {
    if (l > v || r < u || u > v)
        return 0;

    if (u <= l && r <= v)
        return st[id];

    int mid = (l + r) / 2;
    return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
bool ans[maxn];
struct edg {
    int u, v;
} b[maxn * 2];
int pars[maxn], pare[maxn];
vector<int>ask1[maxn], ask2[maxn];
vector<int>canh[maxn];
vector<int>answer[maxn * 2];
bool valid[maxn];
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 = sz(x), q = sz(S);
    for1(i, 0, m - 1)x[i]++, y[i]++;
    for1(i, 0, q - 1)S[i]++, E[i]++, L[i]++, R[i]++;
    for1(i, 1, m) {
        b[i] = {x[i - 1], y[i - 1]};
        canh[max(x[i - 1], y[i - 1])].pb(i);
    }
    for1(i, 0, q - 1)swap(S[i], E[i]);;
    DSU_Tree t1, t2; //t1 for 1->n t2 for n->1
    for1(i, 0, q - 1) {
        ask1[R[i]].pb(i);
    }
    t1.resz(n), t2.resz(n);
    for1(i, 1, n) {
        for (auto v : canh[i]) {
            t1.unite(b[v].u, b[v].v);
        }

        for (auto v : ask1[i]) {
            pars[v] = t1.fs(S[v]);
        }

        canh[i].clear();
    }
    for1(i, 1, m) {
        canh[min(x[i - 1], y[i - 1])].pb(i);
    }
    for1(i, 0, q - 1) {
        ask2[L[i]].pb(i);
    }
    for2(i, n, 1) {
        for (auto v : canh[i]) {
            t2.unite(b[v].u, b[v].v);
        }

        for (auto v : ask2[i]) {
            pare[v] = t2.fs(E[v]);
        }
    }
    t1.dfs(t1.n), t2.dfs(t2.n);
    int nn = t2.n;
    for1(i, 0, q - 1) {
        answer[t1.out[pars[i]]].pb(i);
    }
    for1(i, 1, t1.n) {
        if (t1.rev[i] <= n) {
            update(1, 1, nn, t2.in[t1.rev[i]], i);
        }

        for (auto v : answer[i]) {
            int start = pars[v], ed = pare[v];

            if (get(1, 1, nn, t2.in[ed], t2.out[ed]) >= t1.in[start]) {
                valid[v] = 1;
            }
        }
    }
    vector<int>last;
    for1(i, 0, q - 1)last.pb(valid[i]);
    return last;
}

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