Submission #402838

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
402838	2021-05-12T12:19:53 Z	kshitij_sodani	Toy Train (IOI17_train)	C++14	11 / 100	1712 ms	1936 KB

train

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

#include "train.h"
vector<int> adj[5001];
vector<int> adj2[5001];
vector<int> adj3[5001];
int cyc[5001];
int vis[5001];
int ok=0;
int cur=-1;
void dfs(int no){
	vis[no]=1;
	for(auto j:adj2[no]){
		if(vis[j]==0){
			dfs(j);
		}
		else if(vis[j]==1){
			if(j==cur){
				ok=1;
			}
		}
	}
}
void dfs2(int no){
	vis[no]=1;
	for(auto j:adj[no]){
		if(vis[j]==0){
			dfs2(j);
		}

	}
}
vector<int> who_wins(vector<int> aa, vector<int> bb,vector<int> uu,vector<int> vv) {
	int n=aa.size();
	int m=uu.size();
	for(int i=0;i<m;i++){
		adj[uu[i]].pb(vv[i]);
		//if(bb[uu[i]]==0 and bb[vv[i]]==0){
			adj2[uu[i]].pb(vv[i]);
		//}
	}
	for(int i=0;i<n;i++){
		if(bb[i]==1){
			cur=i;
			for(int j=0;j<n;j++){
				vis[j]=0;
			}
			ok=0;
			dfs(i);
			cyc[i]=ok;
		}
		//else{
		//	cyc[i]=0;
		//}
	}
	vector<int> ans;
	for(int i=0;i<n;i++){
		ans.pb(0);
		for(int j=0;j<n;j++){
			vis[j]=0;
		}
		dfs2(i);
		for(int j=0;j<n;j++){
			if(vis[j]==1 and cyc[j]==1 and bb[j]==1){
				ans[i]=1;
			}
		}

		/*for(int j=i;j<n;j++){
			int st=0;
			int st2=0;
			for(auto ii:adj[j]){
				if(ii==j){
					st=1;
				}
				if(ii==j+1){
					st2=1;
				}
			}
			if(st==1){
				if(st2==0){
					if(bb[j]==1){
						ans[i]=1;
					}
					else{

					}
					break;
				}
				if(aa[j]==0){
					if(bb[j]==0){
						break;
					}
				}
				if(aa[j]==1 and bb[j]==1){

					ans[i]=1;
					break;
				}
			}
		}*/
	}



	return ans;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	357 ms	1348 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	588 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	235 ms	1732 KB	Output is correct
2	Correct	251 ms	1588 KB	Output is correct
3	Correct	289 ms	1656 KB	Output is correct
4	Correct	1395 ms	1616 KB	Output is correct
5	Correct	860 ms	1740 KB	Output is correct
6	Correct	727 ms	1732 KB	Output is correct
7	Correct	908 ms	1704 KB	Output is correct
8	Correct	386 ms	1712 KB	Output is correct
9	Correct	380 ms	1708 KB	Output is correct
10	Correct	488 ms	1732 KB	Output is correct
11	Correct	429 ms	1756 KB	Output is correct
12	Correct	51 ms	1604 KB	Output is correct
13	Correct	1077 ms	1824 KB	Output is correct
14	Correct	1077 ms	1804 KB	Output is correct
15	Correct	1081 ms	1840 KB	Output is correct
16	Correct	1061 ms	1936 KB	Output is correct
17	Correct	1065 ms	1820 KB	Output is correct
18	Correct	533 ms	1568 KB	Output is correct