Submission #263838

#	Time	Username	Problem	Language	Result	Execution time	Memory
263838		arnold518	Toy Train (IOI17_train)	C++14	11 / 100	1746 ms	1792 KiB

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
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51