Submission #535425

#	Time	Username	Problem	Language	Result	Execution time	Memory
535425		mario05092929	Werewolf (IOI18_werewolf)	C++14	100 / 100	1355 ms	136960 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef vector <int> vec;
const int INF = 1e9;
int n,m,Q,uni[200005];
vector <int> v[200005],tvn[200005],tv1[200005];
int p1[200005][18],pn[200005][18];
int in1[200005],inn[200005],out1[200005],outn[200005],co;
int bu[200005];
vector <int> t[800005];

int Find(int x) {return (x == uni[x] ? x : uni[x] = Find(uni[x]));}

void dfs_mark1(int x) {
    in1[x] = ++co;
    for(int i : tv1[x]) dfs_mark1(i);
    out1[x] = co;
}

void dfs_markn(int x) {
    inn[x] = ++co;
    for(int i : tvn[x]) dfs_markn(i);
    outn[x] = co;
}

void build(int x,int l,int r) {
    if(l == r) {
        t[x].push_back(bu[l]);
        return;
    }
    int mid = (l + r) >> 1;
    build(x*2,l,mid), build(x*2+1,mid+1,r);
    for(int i : t[x*2]) t[x].push_back(i);
    for(int i : t[x*2+1]) t[x].push_back(i);
    sort(t[x].begin(),t[x].end());
}

int query(int x,int l,int r,int rl,int rr,int ql,int qr) {
    if(rl <= l&&r <= rr) {
        int it1 = upper_bound(t[x].begin(),t[x].end(),qr)-t[x].begin()-1, it2 = lower_bound(t[x].begin(),t[x].end(),ql)-t[x].begin()-1;
        return (it1-it2 > 0);
    }
    if(rl > r||l > rr) return 0;
    int mid = (l + r) >> 1;
    return (query(x*2,l,mid,rl,rr,ql,qr)||query(x*2+1,mid+1,r,rl,rr,ql,qr));
}

vec check_validity(int N,vec X,vec Y,vec S,vec E,vec L,vec R) {
    n = N, m = X.size(), Q = S.size();
    for(int i = 0;i < m;i++) {
        X[i]++, Y[i]++;
        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }
    for(int i = 0;i < Q;i++) {
        S[i]++, E[i]++, L[i]++, R[i]++;
    }
    pn[n][0] = n, p1[1][0] = 1;
    for(int i = 1;i <= n;i++) uni[i] = i;
    for(int i = 1;i <= n;i++) {
        for(int j : v[i]) {
            if(j < i) {
                if(Find(j) != i) {
                    int tmp = Find(j); uni[tmp] = i;
                    pn[tmp][0] = i, tvn[i].push_back(tmp);
                }
            }
        }
    }
    for(int i = 1;i <= n;i++) uni[i] = i;
    for(int i = n;i >= 1;i--) {
        for(int j : v[i]) {
            if(j > i) {
                if(Find(j) != i) {
                    int tmp = Find(j); uni[tmp] = i;
                    p1[tmp][0] = i, tv1[i].push_back(tmp);
                }
            }
        }
    }
    for(int i = 1;i < 18;i++) {
        for(int j = 1;j <= n;j++) {
            pn[j][i] = pn[pn[j][i-1]][i-1];
            p1[j][i] = p1[p1[j][i-1]][i-1];
        }
    }
    dfs_mark1(1); co = 0;
    dfs_markn(n);
    for(int i = 1;i <= n;i++) bu[inn[i]] = in1[i];
    build(1,1,n);
    vec ans;
    for(int i = 0;i < Q;i++) {
        int l,r,x = E[i],l2,r2;
        for(int j = 17;j >= 0;j--) {
            if(pn[x][j] <= R[i]) x = pn[x][j];
        }
        l = inn[x], r = outn[x]; x = S[i];

        for(int j = 17;j >= 0;j--) {
            if(p1[x][j] >= L[i]) x = p1[x][j];
        }
        l2 = in1[x], r2 = out1[x];
        ans.push_back(query(1,1,n,l,r,l2,r2));
    }
    return ans;
}

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