Submission #758762

#	Time	Username	Problem	Language	Result	Execution time	Memory
758762		alexander707070	Werewolf (IOI18_werewolf)	C++14	15 / 100	4035 ms	56572 KiB

werewolf

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

int n,m,q,tt,num[MAXN],to[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];

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 check(int x,int y){
    for(int i=from[y];i<=len[y];i++){
        if(euler[i]>=num[x] and euler[i]<=to[x])return 1;
    }
    return 0;
}

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;
            }
        }
    }
    dfs2(n,0);

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

        while(S[i]!=1 and up[S[i]]>=L[i]){
            S[i]=up[S[i]];
        }

        while(T[i]!=n and up2[T[i]]<=R[i]){
            T[i]=up2[T[i]];
        }

        ans.push_back(check(S[i],T[i]));
    }

    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:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<maxt[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     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:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int f=0;f<v[i].size();f++){
      |                     ~^~~~~~~~~~~~
werewolf.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int f=0;f<v[i].size();f++){
      |                     ~^~~~~~~~~~~~

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