oj.uz

Submission #758768

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

        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);
            }
        }

        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:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int f=0;f<v[i].size();f++){
      |                     ~^~~~~~~~~~~~
werewolf.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         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 14396 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14500 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 7 ms 14440 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 7 ms 14420 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 14396 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14500 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 7 ms 14440 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 14 ms 15732 KB Output is correct
11 Correct 15 ms 15700 KB Output is correct
12 Correct 11 ms 15696 KB Output is correct
13 Correct 15 ms 15824 KB Output is correct
14 Correct 17 ms 15820 KB Output is correct
15 Correct 16 ms 15820 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 94556 KB Output is correct
2 Correct 983 ms 98064 KB Output is correct
3 Correct 900 ms 104116 KB Output is correct
4 Correct 3947 ms 103212 KB Output is correct
5 Execution timed out 4094 ms 102572 KB Time limit exceeded
6 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 14396 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14500 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 7 ms 14440 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 14 ms 15732 KB Output is correct
11 Correct 15 ms 15700 KB Output is correct
12 Correct 11 ms 15696 KB Output is correct
13 Correct 15 ms 15824 KB Output is correct
14 Correct 17 ms 15820 KB Output is correct
15 Correct 16 ms 15820 KB Output is correct
16 Correct 553 ms 94556 KB Output is correct
17 Correct 983 ms 98064 KB Output is correct
18 Correct 900 ms 104116 KB Output is correct
19 Correct 3947 ms 103212 KB Output is correct
20 Execution timed out 4094 ms 102572 KB Time limit exceeded
21 Halted 0 ms 0 KB -