oj.uz

Submission #423666

# Submission time Handle Problem Language Result Execution time Memory
423666 2021-06-11T11:04:54 Z Pbezz Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 41868 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 2e5+5;
const ll INF = 1e9+7;

vector<vector<ll>>adj(MAXN);
bool state[MAXN][2];
//state[i][0]==true means e possivel chegar a i enquanto human
int l,r,e;
void dfs(ll node, ll wolf){//cout<<node<<" "<<wolf<<endl;

state[node][wolf]=true;

//nao mudar nada
for(auto u:adj[node]){
if(state[u][wolf]==true)continue;

if(wolf==0){
if(u<l)continue;

dfs(u,wolf);

}else{
if(u>r)continue;

dfs(u,wolf);

}

}

if(wolf==0 && state[node][1]==false && node<=r){

state[node][1]=true;
wolf=1;

for(auto u:adj[node]){
if(state[u][wolf]==true)continue;

if(u>r)continue;

dfs(u,wolf);

}




}




}

std::vector<int> check_validity(int N,std::vector<int>X,std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	int Q = S.size(),m=(int)X.size(), i,j;

	for(i=0;i<m;i++){
	adj[X[i]].pb(Y[i]);
	adj[Y[i]].pb(X[i]);
	}

	int s;
	std::vector<int> A(Q);
	for(i=0;i<Q;i++){

	s=S[i]; e=E[i]; l=L[i]; r=R[i];

	for(j=0;j<N;j++){
	state[j][0]=false; state[j][1]=false;
	}

	A[i]=0;

	if(s>=l){
	dfs(s,0);

	if(state[e][1]==true)A[i]=1;

	}
//cout<<endl<<endl;


}
  return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4964 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 5008 KB Output is correct
7 Correct 4 ms 5004 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 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 4 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4964 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 5008 KB Output is correct
7 Correct 4 ms 5004 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 369 ms 5408 KB Output is correct
11 Correct 242 ms 5276 KB Output is correct
12 Correct 30 ms 5540 KB Output is correct
13 Correct 353 ms 5412 KB Output is correct
14 Correct 202 ms 5364 KB Output is correct
15 Correct 265 ms 5648 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4041 ms 41868 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 4 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4964 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 5008 KB Output is correct
7 Correct 4 ms 5004 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 369 ms 5408 KB Output is correct
11 Correct 242 ms 5276 KB Output is correct
12 Correct 30 ms 5540 KB Output is correct
13 Correct 353 ms 5412 KB Output is correct
14 Correct 202 ms 5364 KB Output is correct
15 Correct 265 ms 5648 KB Output is correct
16 Execution timed out 4041 ms 41868 KB Time limit exceeded
17 Halted 0 ms 0 KB -