oj.uz

Submission #758762

# Submission time Handle Problem Language Result Execution time Memory
758762 2023-06-15T09:05:42 Z alexander707070 Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 56572 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14408 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14432 KB Output is correct
6 Correct 7 ms 14408 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14380 KB Output is correct
9 Correct 7 ms 14456 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14408 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14432 KB Output is correct
6 Correct 7 ms 14408 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14380 KB Output is correct
9 Correct 7 ms 14456 KB Output is correct
10 Correct 13 ms 15092 KB Output is correct
11 Correct 12 ms 14988 KB Output is correct
12 Correct 11 ms 14960 KB Output is correct
13 Correct 18 ms 15176 KB Output is correct
14 Correct 19 ms 15152 KB Output is correct
15 Correct 17 ms 15188 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 53900 KB Output is correct
2 Execution timed out 4035 ms 56572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14408 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14432 KB Output is correct
6 Correct 7 ms 14408 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14380 KB Output is correct
9 Correct 7 ms 14456 KB Output is correct
10 Correct 13 ms 15092 KB Output is correct
11 Correct 12 ms 14988 KB Output is correct
12 Correct 11 ms 14960 KB Output is correct
13 Correct 18 ms 15176 KB Output is correct
14 Correct 19 ms 15152 KB Output is correct
15 Correct 17 ms 15188 KB Output is correct
16 Correct 255 ms 53900 KB Output is correct
17 Execution timed out 4035 ms 56572 KB Time limit exceeded
18 Halted 0 ms 0 KB -