Submission #824989

#	Time	Username	Problem	Language	Result	Execution time	Memory
824989		phoenix	Werewolf (IOI18_werewolf)	C++17	100 / 100	522 ms	87852 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"

using namespace std;

struct SegTree {
    const static int N = (1 << 18);
    vector<int> t;
    SegTree() {
        t.assign(2 * N, -1);
    }
    void update(int pos, int val) {
        for(t[pos += N] = val; pos > 1; pos >>= 1) {
            t[pos >> 1] = max(t[pos], t[(pos ^ 1)]);
        }
    }
    int get(int ql, int qr) {
        int res = -1;
        for(ql += N, qr += N + 1; ql < qr; ql >>= 1, qr >>= 1) {
            if(ql & 1) res = max(t[ql++], res);
            if(qr & 1) res = max(t[--qr], res);
        }
        return res;
    }
};

struct DSU {
    vector<int> p, r;
    DSU(int n) {
        p.assign(n, 0);
        r.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        return p[x] = (p[x] == x ? x : find(p[x]));
    }
    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if(u == v) return;
        p[v] = u;
    }
};
const int N = 200010;

struct Tree {
    vector<int> g[N];
    vector<int> order;
    int tin[N], tout[N], anc[N][18];

    void dfs(int s, int p) {
        tin[s] = (int)order.size();
        order.push_back(s);
        anc[s][0] = p;
        for(int i = 1; i < 18; i++) 
            anc[s][i] = anc[anc[s][i - 1]][i - 1];
            
        for(int to : g[s]) {
            if(to == p) continue;
            dfs(to, s);
        }
        tout[s] = (int)order.size() - 1;
    }
};

Tree LL, RR;
vector<int> g[N];
SegTree st;

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                  vector<int> S, vector<int> T,
                                  vector<int> L, vector<int> R) {
    int m = (int)X.size(), q = (int)S.size();
    for(int i = 0; i < m; i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    DSU ds(N);
    for(int i = 0; i < N; i++) {
        for(int to : g[i]) {
            to = ds.find(to);
            if(to >= i) continue;
            ds.merge(i, to);
            RR.g[i].push_back(to);
        }
    }
    ds = DSU(N);
    for(int i = N - 1; i >= 0; i--) {
        for(int to : g[i]) {
            to = ds.find(to);
            if(to <= i) continue;
            ds.merge(i, to);
            LL.g[i].push_back(to);
        }
    }
    LL.dfs(0, 0);
    RR.dfs(N - 1, N - 1);
    vector<int> qr[N];
    vector<int> res(q);

    for(int i = 0; i < q; i++) {
        for(int k = 17; k >= 0; k--) {
            if(LL.anc[S[i]][k] >= L[i]) 
                S[i] = LL.anc[S[i]][k];
            if(RR.anc[T[i]][k] <= R[i])
                T[i] = RR.anc[T[i]][k];
        }
        qr[LL.tout[S[i]]].push_back(i);
    }
    for(int i = 0; i < N; i++) {
        int x = LL.order[i];
        st.update(RR.tin[x], i);
        for(int query : qr[i]) {
            int l = RR.tin[T[query]], r = RR.tout[T[query]];
            res[query] = (st.get(l, r) >= LL.tin[S[query]]); 
        }
    }   
    return res;
}

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