Submission #72901

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
72901	2018-08-27T08:02:19 Z	mr_banana	Toy Train (IOI17_train)	C++17	11 / 100	367 ms	26436 KB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int MN=5000+100;
bool g[MN][MN];
vector<int> adj[MN],radj[MN];
vector<int> topol;
bool mark[MN];
int cmp[MN],szcmp[MN];
int n,m;
void dfs(int v){
	mark[v]=1;
	for(int u:adj[v]){
		if(!mark[u]){
			dfs(u);
		}
	}
	topol.push_back(v);
}
void dfs2(int v,int cmpn){
	mark[v]=1;
	cmp[v]=cmpn;
	szcmp[cmpn]++;
	for(int u:radj[v]){
		if(!mark[u]){
			dfs2(u,cmpn);
		}
	}
}
void scc(){
	for(int i=0;i<n;i++){
		if(!mark[i]){
			dfs(i);
		}
	}
	memset(mark,0,sizeof mark);
	int cnt=0;
	for(int i=n-1;i>=0;i--){
		if(!mark[topol[i]]){
			dfs2(topol[i],cnt);
			cnt++;
		}
	}
}
void dfs3(int v){
	mark[v]=1;
	for(int i=0;i<n;i++){
		if(!mark[i] && g[i][v]){
			dfs3(i);
		}
	}
}
vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v) {
	vector<int> res(a.size());
	n=a.size(),m=v.size();
	for(int i=0;i<m;i++){
		g[u[i]][v[i]]=1;
		adj[u[i]].push_back(v[i]);
		radj[v[i]].push_back(u[i]);
	}
	scc();
	memset(mark,0,sizeof mark);
	for(int i=0;i<n;i++){
		if(!mark[i] && r[i] && (szcmp[cmp[i]]>1 || g[i][i])){
			dfs3(i);
		}
	}
	for(int i=0;i<n;i++){
		res[i]=mark[i];
	}
	return res;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	135 ms	21624 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	3 ms	21624 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	31 ms	21624 KB	Output is correct
2	Correct	25 ms	22120 KB	Output is correct
3	Correct	26 ms	23132 KB	Output is correct
4	Correct	177 ms	26436 KB	Output is correct
5	Correct	158 ms	26436 KB	Output is correct
6	Correct	46 ms	26436 KB	Output is correct
7	Correct	277 ms	26436 KB	Output is correct
8	Correct	167 ms	26436 KB	Output is correct
9	Correct	38 ms	26436 KB	Output is correct
10	Correct	367 ms	26436 KB	Output is correct
11	Correct	202 ms	26436 KB	Output is correct
12	Correct	30 ms	26436 KB	Output is correct
13	Correct	146 ms	26436 KB	Output is correct
14	Correct	133 ms	26436 KB	Output is correct
15	Correct	130 ms	26436 KB	Output is correct
16	Correct	147 ms	26436 KB	Output is correct
17	Correct	140 ms	26436 KB	Output is correct
18	Correct	25 ms	26436 KB	Output is correct