Submission #587135

#	Time	Username	Problem	Language	Result	Execution time	Memory
587135		alirezasamimi100	Werewolf (IOI18_werewolf)	C++17	100 / 100	613 ms	105388 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using pii = pair<int, int>;

const int N = 2e5 + 10;

vector<int> rad[2][N],adj[2][N],QL[N],QR[N],QU[2][N];
int st[2][N],fn[2][N],p[2][N],T[2],rv[2][N],f[N];

int gp(int c, int x){
    return p[c][x]!=x?p[c][x]=gp(c,p[c][x]):x;
}

void uni(int c, int v, int u){
    u=gp(c,u);
    if(v==u) return;
    adj[c][v].pb(u);
    p[c][u]=v;
}

void dfs(int c, int v){
    st[c][v]=++T[c];
    rv[c][T[c]]=v;
    for(int u : adj[c][v]) dfs(c,u);
    fn[c][v]=T[c];
}

void upd(int t, int x){
    for(; t<N; t+=t&-t) f[t]+=x;
}

int gt(int t, int x=0){
    for(; t; t-=t&-t) x+=f[t];
    return x;
}

int get(int l, int r){
    return gt(r)-gt(l-1);
}

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=X.size(), Q=S.size();
    for(int i=0; i<Q; i++){
        QL[L[i]].pb(i);
        QR[R[i]].pb(i);
    }
    vector<int> A(Q);
    for(int i=0; i<M; i++){
        if(X[i]>Y[i]) swap(X[i],Y[i]);
        rad[0][Y[i]].pb(X[i]);
        rad[1][X[i]].pb(Y[i]);
    }
    for(int i=0; i<N; i++) p[0][i]=p[1][i]=i;
    for(int i=0; i<N; i++){
        for(int j : rad[0][i]) uni(0,i,j);
        for(int j : QR[i]){
            E[j]=gp(0,E[j]);
        }
    }
    for(int i=N; i--; ){
        for(int j : rad[1][i]) uni(1,i,j);
        for(int j : QL[i]){
            S[j]=gp(1,S[j]);
        }
    }
    dfs(0,N-1);
    dfs(1,0);
    for(int i=0; i<Q; i++){
        QU[0][st[0][E[i]]-1].pb(i);
        QU[1][fn[0][E[i]]].pb(i);
    }
    for(int i=1; i<=N; i++){
        upd(st[1][rv[0][i]],1);
        for(int j : QU[0][i]) A[j]-=get(st[1][S[j]],fn[1][S[j]]);
        for(int j : QU[1][i]) A[j]+=get(st[1][S[j]],fn[1][S[j]]);
    }
    for(int i=0; i<Q; i++) if(A[i]) A[i]=1;
    return A;
}

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