Submission #358544

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
358544	2021-01-25T18:47:22 Z	Kerim	Toy Train (IOI17_train)	C++17	11 / 100	218 ms	11756 KB

train

#include "train.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int col[MAXN],vis[MAXN],res,n,m;
vector<int>adj[MAXN],inv[MAXN],ans;
bool dfs(int nd,int root){
	if(vis[nd])return (nd==root);
	vis[nd]=1;
	tr(it,adj[nd])
		if(dfs(*it,root))return 1;
	return 0;
}
void dfs1(int nd){
	if(ans[nd])return;
	ans[nd]=1;
	tr(it,inv[nd])
		dfs1(*it);	
}
int same[MAXN],go[MAXN];
vector<int> who_wins(vector<int> a, vector<int> r,vector<int> u,vector<int> v) {
	n=int(a.size());m=int(u.size());
	for(int i=0;i<n;i++)col[i]=r[i];
	int subtask3=1,subtask4=1,subtask1=1;
	for(int i=0;i<n;i++)subtask3&=(a[i]),subtask4&=(!a[i]);
	ans.resize(n);for(int i=0;i<n;i++)ans[i]=0;
	for(int i=0;i<m;i++)
		adj[u[i]].pb(v[i]),inv[v[i]].pb(u[i]),subtask1&=(v[i]==u[i] or v[i]==u[i]+1);
	if(subtask1){
		for(int i=0;i<n;i++)
			tr(it,adj[i])
				same[i]|=(*it==i),go[i]|=(*it==i+1);
		for(int i=0;i<n;i++){
			int j=i;
			while(1){
				if(same[j] and col[j]==a[j]){
					ans.pb(a[j]);
					break;
				}
				if(go[j])
					j++;
				else{
					ans.pb(0);	
					break;
				}
			}
		}
	}
	else if(subtask3){
		for(int i=0;i<n;i++)
			if(col[i]){
				for(int j=0;j<n;j++)vis[j]=0;
				int ret=dfs(i,i);
				if(ret)
					dfs1(i);
			}
	}
	else if(subtask4){
			
	}
	else assert(0);
	return ans;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	8 ms	5740 KB	WA in grader: Wrong returned array size
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	10 ms	9964 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	6016 KB	Output is correct
2	Correct	32 ms	6124 KB	Output is correct
3	Correct	59 ms	5996 KB	Output is correct
4	Correct	142 ms	6124 KB	Output is correct
5	Correct	32 ms	5996 KB	Output is correct
6	Correct	87 ms	5996 KB	Output is correct
7	Correct	218 ms	6124 KB	Output is correct
8	Correct	12 ms	5996 KB	Output is correct
9	Correct	11 ms	5868 KB	Output is correct
10	Correct	14 ms	5868 KB	Output is correct
11	Correct	11 ms	5868 KB	Output is correct
12	Correct	11 ms	5868 KB	Output is correct
13	Correct	12 ms	5996 KB	Output is correct
14	Correct	12 ms	5996 KB	Output is correct
15	Correct	12 ms	5996 KB	Output is correct
16	Correct	12 ms	5996 KB	Output is correct
17	Correct	12 ms	5996 KB	Output is correct
18	Correct	174 ms	5868 KB	Output is correct