oj.uz

Submission #420386

# Submission time Handle Problem Language Result Execution time Memory
420386 2021-06-08T10:21:52 Z A_D Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 30500 KB 
#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;
const int N=2e5+100;
vector<int> g[N];
bool vis[N][2];
int l,r;
bool ok(int u,int f)
{
    if(f==1){
        if(u>r)return 0;
    }
    else{
        if(u<l)return 0;
    }
    return 1;
}
void dfs(int u,int f)
{
    if(ok(u,f)==0)return;
//    cout<<u<<" "<<f<<endl;
    vis[u][f]=1;
    if(f==0){
        dfs(u,1);
    }
    for(auto x:g[u]){
        if(vis[x][f])continue;
        dfs(x,f);
    }
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
    vector<int> ret;
    for(int i=0;i<X.size();i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    for(int t=0;t<S.size();t++){
        for(int i=0;i<=N;i++){
            vis[i][0]=0;
            vis[i][1]=0;
        }
        l=L[t];
        r=R[t];
        dfs(S[t],0);
  //      cout<<"\n\n";
        if(vis[E[t]][1]){
            ret.push_back(1);
        }
        else{
            ret.push_back(0);
        }
    }
    return ret;
}

/*


6 6 3
5 1
1 2
1 3
3 4
0 3
2 5
4 2 1 2
4 2 2 2
5 4 3 4




*/

Compilation message

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:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<X.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int t=0;t<S.size();t++){
      |                 ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4996 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 5000 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4988 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4996 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 5000 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4988 KB Output is correct
10 Correct 377 ms 5384 KB Output is correct
11 Correct 251 ms 5352 KB Output is correct
12 Correct 26 ms 5484 KB Output is correct
13 Correct 319 ms 5372 KB Output is correct
14 Correct 186 ms 5340 KB Output is correct
15 Correct 340 ms 5536 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4064 ms 30500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4996 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 5000 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4988 KB Output is correct
10 Correct 377 ms 5384 KB Output is correct
11 Correct 251 ms 5352 KB Output is correct
12 Correct 26 ms 5484 KB Output is correct
13 Correct 319 ms 5372 KB Output is correct
14 Correct 186 ms 5340 KB Output is correct
15 Correct 340 ms 5536 KB Output is correct
16 Execution timed out 4064 ms 30500 KB Time limit exceeded
17 Halted 0 ms 0 KB -