Submission #519206

#	Time	Username	Problem	Language	Result	Execution time	Memory
519206		oneloveforever	Werewolf (IOI18_werewolf)	C++14	49 / 100	4046 ms	110064 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int logn = log2(maxn) + 1;
vector<int> e[maxn] , adj[maxn] , radj[maxn];
int lab[maxn];
int in[2][maxn] , out[2][maxn] , id[2][maxn];
int nTime = 0;
int P[2][maxn][logn];
int n;
#define pb push_back
void DFS(int u , int par , vector<int> adj[] , int in[] , int out[] , int id[] ,  int P[maxn][logn]){
    P[u][0] = par;
    for(int i = 1 ; i < logn ; ++i){
        if(P[u][i - 1] >= 0 && P[u][i - 1] < n)P[u][i] = P[P[u][i - 1]][i - 1];
        else P[u][i] = P[u][i - 1];
    }
    in[u] = ++nTime;
    id[nTime] = u;
    for(int c : adj[u]){
        DFS(c , u , adj , in , out, id , P);
    }
    out[u] = nTime;
}
int bit[maxn];
 
void add(int x){
    for(;x <= n ;x += x & -x){
        bit[x]++;
    }
}
int query(int x){
    int res = 0;
    for( ; x > 0 ; x &= x - 1){
        res += bit[x];
    }
    return res;
}
 
vector<tuple<int,int,int,int>> a[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) {
    n = _n;
    for(int i = 0 ; i < (int)X.size() ; ++i){
        e[X[i]].pb(Y[i]);
        e[Y[i]].pb(X[i]);
    }
    fill_n(lab,maxn,-1);
    function<int(int)> FindLab = [&](int u){
        return lab[u] < 0 ? u :  FindLab(lab[u]);
    };
    auto add = [&](int x , int y , vector<int> adj[]){
        int s = FindLab(x);
        int d = FindLab(y);
        if(s == d)return;
        lab[d] = s;
        adj[s].pb(d);
    };
    for(int i = 0 ; i < n ; ++i){
        for(int c : e[i]){
            if(c < i)add(i , c , radj);
        }
    }
    fill_n(lab,maxn,-1);
    for(int i = n - 1 ; i >= 0 ; --i){
        for(int c : e[i]){
            if(c > i)add(i , c , adj);
        }
    }
    DFS(0 , -1 , adj , in[0] , out[0] , id[0] , P[0]);
    nTime = 0;
    DFS(n - 1 , n , radj , in[1] , out[1] , id[1] , P[1]);
    int q = S.size();
    vector<int> res(q , 0);
    for(int i = 0 ; i < q ; ++i){
        int s = S[i];int e = E[i];
        for(int j = logn - 1 ; j >= 0 ; --j){
            if(P[0][s][j] >= L[i])s = P[0][s][j];
            if(P[1][e][j] <= R[i])e = P[1][e][j];
        }
        a[in[0][s] - 1].emplace_back(-1 , in[1][e] , out[1][e] , i);
        a[out[0][s]].emplace_back(1 , in[1][e] , out[1][e] , i);
    }
    for(int i = 1 ; i <= n ; ++i){
        ::add(in[1][id[0][i]]);
//        cout << in[1][id[0][i]] << endl;
        for(auto & c : a[i]){
            int delta , l , r , id;
            tie(delta , l , r , id) = c;
            res[id] += delta * (query(r) - query(l - 1));
        }
    }
    for(int i = 0 ; i < q ; ++i){
        res[i] = res[i] > 0;
    }
    return res;
}

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