Submission #758771

#	Time	Username	Problem	Language	Result	Execution time	Memory
758771		alexander707070	Werewolf (IOI18_werewolf)	C++14	100 / 100	1503 ms	127500 KiB

werewolf

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

struct event{
    int l,r,id;
};

int n,m,q,tt,num[MAXN],to[MAXN],res[MAXN];
vector<int> v[MAXN],mint[MAXN],maxt[MAXN],ans,bro;
int dsu[MAXN],euler[MAXN],from[MAXN],len[MAXN];
int up[MAXN],up2[MAXN];
vector<event> qr[MAXN];

int root(int x){
    if(dsu[x]==x)return x;
    dsu[x]=root(dsu[x]);
    return dsu[x];
}

void setdsu(){
    for(int i=1;i<=n;i++){
        dsu[i]=i;
    }
}

void dfs(int x,int p){
    tt++; num[x]=to[x]=tt; up[x]=p;
    for(int i=0;i<maxt[x].size();i++){
        dfs(maxt[x][i],x);
    }
    to[x]=tt;
}

void dfs2(int x,int p){
    tt++; euler[tt]=num[x];
    from[x]=tt; up2[x]=p;
    for(int i=0;i<mint[x].size();i++){
        dfs2(mint[x][i],x);
    }
    len[x]=tt;
}

int dp[MAXN][25],dp2[MAXN][25];
bool li[MAXN][25],li2[MAXN][25];

int ff(int x,int p){
    if(up[x]==0)return 0;
    if(p==0)return up[x];

    if(li[x][p])return dp[x][p];
    li[x][p]=true;

    dp[x][p]=ff(ff(x,p-1),p-1);
    return dp[x][p];
}

int ff2(int x,int p){
    if(up2[x]==0)return 0;
    if(p==0)return up2[x];

    if(li2[x][p])return dp2[x][p];
    li2[x][p]=true;

    dp2[x][p]=ff2(ff2(x,p-1),p-1);
    return dp2[x][p];
}

int fenwick[MAXN];

void update(int x){
    while(x<=n){
        fenwick[x]++;
        x+=(x & (-x));
    }
}

int sum(int x){
    int res=0;
    while(x>=1){
        res+=fenwick[x];
        x-=(x & (-x));
    }
    return res;
}

void check(int x,int y,int id){
    qr[from[y]-1].push_back({num[x],to[x],id});
    qr[len[y]].push_back({num[x],to[x],id});
}

vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> T,vector<int> L,vector<int> R){
    n=N; m=int(X.size()); q=int(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]);
    }

    setdsu();
    for(int i=n;i>=1;i--){
        for(int f=0;f<v[i].size();f++){
            if(root(v[i][f])>i){
                maxt[i].push_back(root(v[i][f]));
                dsu[root(v[i][f])]=i;
            }
        }
    }
    dfs(1,0);

    setdsu();
    for(int i=1;i<=n;i++){
        for(int f=0;f<v[i].size();f++){
            if(root(v[i][f])<i){
                mint[i].push_back(root(v[i][f]));
                dsu[root(v[i][f])]=i;
            }
        }
    }
    tt=0;
    dfs2(n,0);

    for(int i=0;i<q;i++){
        S[i]++; T[i]++; L[i]++; R[i]++;

        for(int f=24;f>=0;f--){
            if(ff(S[i],f)!=0 and ff(S[i],f)>=L[i]){
                S[i]=ff(S[i],f);
            }
        }

        for(int f=24;f>=0;f--){
            if(ff2(T[i],f)!=0 and ff2(T[i],f)<=R[i]){
                T[i]=ff2(T[i],f);
            }
        }

        check(S[i],T[i],i);
        res[i]=-1;
    }
    
    for(int i=0;i<=n;i++){
        if(i!=0)update(euler[i]);

        for(int f=0;f<qr[i].size();f++){
            if(res[qr[i][f].id]==-1){
                res[qr[i][f].id]=sum(qr[i][f].r)-sum(qr[i][f].l-1);
            }else{
                res[qr[i][f].id]=sum(qr[i][f].r)-sum(qr[i][f].l-1)-res[qr[i][f].id];
            }
        }
    }

    for(int i=0;i<q;i++){
        if(res[i]>0)ans.push_back(1);
        else ans.push_back(0);
    }

    return ans;
}

/*
int main(){
    bro=check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
{4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
    cout<<bro[0]<<" "<<bro[1]<<" "<<bro[2]<<"\n";
}
*/

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<maxt[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<mint[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int f=0;f<v[i].size();f++){
      |                     ~^~~~~~~~~~~~
werewolf.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for(int f=0;f<v[i].size();f++){
      |                     ~^~~~~~~~~~~~
werewolf.cpp:146:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for(int f=0;f<qr[i].size();f++){
      |                     ~^~~~~~~~~~~~~

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