Submission #109022

#	Time	Username	Problem	Language	Result	Execution time	Memory
109022		PeppaPig	Werewolf (IOI18_werewolf)	C++14	100 / 100	2494 ms	220804 KiB

werewolf

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

using namespace std;

const int N = 2e5+5;

int n, m, q;

struct node {
    int d;
    node *l, *r;
    node(int d, node *l, node *r) : d(d), l(l), r(r) { }
};

node* newleaf(int d) { return new node(d, nullptr, nullptr); }
node* newpar(node *l, node *r) { return new node(l->d + r->d, l, r); }

node* build(int l = 1, int r = n) {
    if(l == r) return newleaf(0);
    int mid = (l + r) >> 1;
    return newpar(build(l, mid), build(mid+1, r));
}

node* update(node *p, int x, int l = 1, int r = n) {
    if(l == r) return newleaf(p->d + 1);
    int mid = (l + r) >> 1;
    if(x <= mid) return newpar(update(p->l, x, l, mid), p->r);
    else return newpar(p->l, update(p->r, x, mid+1, r));
}

int query(node *pl, node *pr, int x, int y, int l = 1, int r = n) {
    if(x > r || l > y) return 0;
    if(x <= l && r <= y) return pr->d - pl->d;
    int mid = (l + r) >> 1;
    return query(pl->l, pr->l, x, y, l, mid) + query(pl->r, pr->r, x, y, mid+1, r);
}

node* t[N];

int dsu[N], hpar[N][18], wpar[N][18];
int hin[N], hout[N], hpos[N];
int win[N], wout[N], wpos[N];
vector<int> g[N], hg[N], wg[N];

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

void gen_human(int u, int p) {
    static int hidx = 0;
    hin[u] = ++hidx, hpos[hidx] = u;
    hpar[u][0] = p;
    for(int i = 1; i <= 17; i++) hpar[u][i] = hpar[hpar[u][i-1]][i-1];
    for(int v : hg[u]) if(v != p) gen_human(v, u);
    hout[u] = hidx;
}

void gen_werewolf(int u, int p) {
    static int widx = 0;
    win[u] = ++widx, wpos[widx] = u;
    wpar[u][0] = p;
    for(int i = 1; i <= 17; i++) wpar[u][i] = wpar[wpar[u][i-1]][i-1];
    for(int v : wg[u]) if(v != p) gen_werewolf(v, u);
    wout[u] = widx;
}

vector<int> check_validity(int _n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n = _n, m = X.size(), q = S.size();

    for(int i = 0; i < m; i++) {
        g[X[i]+1].emplace_back(Y[i]+1);
        g[Y[i]+1].emplace_back(X[i]+1);
    }
    iota(dsu, dsu+N, 0);
    for(int u = n; u; u--) for(int v : g[u]) if(v > u) {
        int pv = find(v);
        if(pv == u) continue;
        hg[u].emplace_back(pv), hg[pv].emplace_back(u);
        dsu[pv] = u;
    }
    iota(dsu, dsu+N, 0);
    for(int u = 1; u <= n; u++) for(int v : g[u]) if(v < u) {
        int pv = find(v);
        if(pv == u) continue;
        wg[u].emplace_back(pv), wg[pv].emplace_back(u);
        dsu[pv] = u;
    }

    gen_human(1, 0), gen_werewolf(n, 0);
    t[0] = build();
    for(int i = 1; i <= n; i++) t[i] = update(t[i-1], win[hpos[i]]);

    vector<int> ret;
    for(int T = 0; T < q; T++) {
        int s = S[T]+1, e = E[T]+1;
        for(int i = 17; ~i; i--) if(hpar[s][i] && hpar[s][i] >= L[T]+1) s = hpar[s][i];
        for(int i = 17; ~i; i--) if(wpar[e][i] && wpar[e][i] <= R[T]+1) e = wpar[e][i];
        if(query(t[hin[s]-1], t[hout[s]], win[e], wout[e])) ret.emplace_back(1);
        else ret.emplace_back(0);
    }

    return ret;
}

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