Submission #263838

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
263838	2020-08-14T02:36:15 Z	arnold518	Toy Train (IOI17_train)	C++14	11 / 100	1746 ms	1792 KB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5000;
const int MAXM = 20000;

int N, M, A[MAXN+10], R[MAXN+10], ans[MAXN+10];
vector<int> adj[MAXN+10], radj[MAXN+10];

bool vis[MAXN+10];

void dfs(int now)
{
	vis[now]=1;
	for(int nxt : adj[now])
	{
		if(vis[nxt]) continue;
		dfs(nxt);
	}
}

void rdfs(int now)
{
	vis[now]=1;
	for(int nxt : radj[now])
	{
		if(vis[nxt]) continue;
		rdfs(nxt);
	}
}

vector<int> who_wins(vector<int> _A, vector<int> _R, vector<int> _U, vector<int> _V)
{
	N=_A.size(); M=_U.size();
	for(int i=1; i<=N; i++)
	{
		A[i]=_A[i-1];
		R[i]=_R[i-1];
	}
	for(int i=0; i<M; i++)
	{
		int u=_U[i]+1, v=_V[i]+1;
		adj[u].push_back(v);
		radj[v].push_back(u);
	}

	for(int i=1; i<=N; i++)
	{
		if(!R[i]) continue;
		for(int j=1; j<=N; j++) vis[j]=0;
		dfs(i);
		bool flag=false;
		for(auto nxt : radj[i])
		{
			if(vis[nxt])
			{
				flag=true;
				break;
			}
		}
		if(!flag) continue;
		for(int j=1; j<=N; j++) vis[j]=0; 
		rdfs(i);
		for(int j=1; j<=N; j++) if(vis[j]) ans[j]=1;
	}

	vector<int> _ans(N);
	for(int i=1; i<=N; i++) _ans[i-1]=ans[i];
	return _ans;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	163 ms	1296 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	512 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	13 ms	1536 KB	Output is correct
2	Correct	30 ms	1696 KB	Output is correct
3	Correct	52 ms	1784 KB	Output is correct
4	Correct	580 ms	1764 KB	Output is correct
5	Correct	74 ms	1740 KB	Output is correct
6	Correct	82 ms	1688 KB	Output is correct
7	Correct	568 ms	1676 KB	Output is correct
8	Correct	12 ms	1664 KB	Output is correct
9	Correct	12 ms	1664 KB	Output is correct
10	Correct	14 ms	1636 KB	Output is correct
11	Correct	10 ms	1600 KB	Output is correct
12	Correct	10 ms	1536 KB	Output is correct
13	Correct	10 ms	1792 KB	Output is correct
14	Correct	10 ms	1792 KB	Output is correct
15	Correct	10 ms	1792 KB	Output is correct
16	Correct	10 ms	1792 KB	Output is correct
17	Correct	13 ms	1792 KB	Output is correct
18	Correct	162 ms	1388 KB	Output is correct