oj.uz

Submission #82518

# Submission time Handle Problem Language Result Execution time Memory
82518 2018-10-31T09:18:33 Z farukkastamonuda Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 23244 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000009
#define md 1000000007
#define li 200005
#define mp make_pair
#define pb push_back
#define mid (start+end)/2
using namespace std;
int vis[li][2];
queue< pair<int,int> > q;
vector<int> v[li],ans,genel,x1,yy1,s1,e1,l1,r1;
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
	for(int i=0;i<(int)S.size();i++){
		//cout<<"tama: : "<<S[i]<<endl;
		for(int j=0;j<N;j++) v[j].clear();
		memset(vis,0,sizeof(vis));
		while(!q.empty()) q.pop();
		for(int j=0;j<(int)X.size();j++){
			v[X[j]].pb(Y[j]);
			v[Y[j]].pb(X[j]);
		}
		if(S[i]<L[i]) {ans.pb(0);continue;}
		if(S[i]>=L[i] && S[i]<=R[i]) q.push(mp(S[i],1));
		q.push(mp(S[i],0));
		int flag=0;
		while(!q.empty()){
			pair<int,int> temp=q.front();
			q.pop();
			int seh=temp.fi;
			int tur=temp.se;
			if(tur==0 && seh<L[i]) continue;
			if(tur==1 && seh>R[i]) continue;
			if(vis[seh][tur]==1) continue;
			if(seh==E[i] && tur==1){
				flag=1;
				break;
			}
			vis[seh][tur]=1;
			for(int j=0;j<(int)v[seh].size();j++){
				int go=v[seh][j];
				if(go>=L[i] && go<=R[i]) q.push(mp(go,1));
				q.push(mp(go,tur));
			}
		}
		if(flag==1) ans.pb(1);
		else ans.pb(0);
	}
	return ans;
}
//~ int main(){
	//~ x1.pb(5),x1.pb(1),x1.pb(1),x1.pb(3),x1.pb(3),x1.pb(5);
	//~ yy1.pb(1),yy1.pb(2),yy1.pb(3),yy1.pb(4),yy1.pb(0),yy1.pb(2);
	//~ s1.pb(4),s1.pb(4),s1.pb(5);
	//~ e1.pb(2),e1.pb(2),e1.pb(4);
	//~ l1.pb(1),l1.pb(2),l1.pb(3);
	//~ r1.pb(2),r1.pb(2),r1.pb(4);
	//~ genel=check_validity(6,x1,yy1,s1,e1,l1,r1);
	//~ for(int i=0;i<(int)genel.size();i++) cout<<genel[i]<<endl;
	//~ return 0;
//~ }

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6648 KB Output is correct
2 Correct 17 ms 6652 KB Output is correct
3 Correct 18 ms 6892 KB Output is correct
4 Correct 18 ms 6900 KB Output is correct
5 Correct 17 ms 6900 KB Output is correct
6 Correct 16 ms 6900 KB Output is correct
7 Correct 16 ms 6900 KB Output is correct
8 Correct 16 ms 6900 KB Output is correct
9 Correct 12 ms 6900 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6648 KB Output is correct
2 Correct 17 ms 6652 KB Output is correct
3 Correct 18 ms 6892 KB Output is correct
4 Correct 18 ms 6900 KB Output is correct
5 Correct 17 ms 6900 KB Output is correct
6 Correct 16 ms 6900 KB Output is correct
7 Correct 16 ms 6900 KB Output is correct
8 Correct 16 ms 6900 KB Output is correct
9 Correct 12 ms 6900 KB Output is correct
10 Correct 869 ms 7392 KB Output is correct
11 Correct 771 ms 7552 KB Output is correct
12 Correct 455 ms 7616 KB Output is correct
13 Correct 743 ms 7924 KB Output is correct
14 Correct 664 ms 7924 KB Output is correct
15 Correct 1259 ms 8144 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6648 KB Output is correct
2 Correct 17 ms 6652 KB Output is correct
3 Correct 18 ms 6892 KB Output is correct
4 Correct 18 ms 6900 KB Output is correct
5 Correct 17 ms 6900 KB Output is correct
6 Correct 16 ms 6900 KB Output is correct
7 Correct 16 ms 6900 KB Output is correct
8 Correct 16 ms 6900 KB Output is correct
9 Correct 12 ms 6900 KB Output is correct
10 Correct 869 ms 7392 KB Output is correct
11 Correct 771 ms 7552 KB Output is correct
12 Correct 455 ms 7616 KB Output is correct
13 Correct 743 ms 7924 KB Output is correct
14 Correct 664 ms 7924 KB Output is correct
15 Correct 1259 ms 8144 KB Output is correct
16 Execution timed out 4019 ms 23244 KB Time limit exceeded
17 Halted 0 ms 0 KB -