Submission #358543

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
358543	2021-01-25T18:37:23 Z	Kerim	Toy Train (IOI17_train)	C++17	11 / 100	222 ms	11116 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);	
}
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;
	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;
	if(subtask3){
		for(int i=0;i<m;i++)
			adj[u[i]].pb(v[i]),inv[v[i]].pb(u[i]);
		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 assert(0);
	return ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	10 ms	10092 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	17 ms	6252 KB	Output is correct
2	Correct	34 ms	6252 KB	Output is correct
3	Correct	58 ms	6380 KB	Output is correct
4	Correct	145 ms	6248 KB	Output is correct
5	Correct	33 ms	6252 KB	Output is correct
6	Correct	86 ms	6124 KB	Output is correct
7	Correct	222 ms	6152 KB	Output is correct
8	Correct	12 ms	6148 KB	Output is correct
9	Correct	12 ms	6124 KB	Output is correct
10	Correct	14 ms	6124 KB	Output is correct
11	Correct	11 ms	6124 KB	Output is correct
12	Correct	14 ms	5996 KB	Output is correct
13	Correct	14 ms	6252 KB	Output is correct
14	Correct	16 ms	6252 KB	Output is correct
15	Correct	15 ms	6252 KB	Output is correct
16	Correct	12 ms	6252 KB	Output is correct
17	Correct	12 ms	6252 KB	Output is correct
18	Correct	183 ms	5868 KB	Output is correct