Submission #263861

#	Time	Username	Problem	Language	Result	Execution time	Memory
263861		arnold518	Toy Train (IOI17_train)	C++14	5 / 100	11 ms	1732 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];
int nxt[MAXN+10];

bool vis[MAXN+10];

void dfs(int now)
{
	vis[now]=1;
	for(int nxt : adj[now])
	{
		if(vis[nxt]) continue;
		if(R[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(adj[i].size()==1)
		{
			nxt[i]=adj[i][0];
			continue;
		}
		if(A[i])
		{
			if(R[i]) nxt[i]=i;
			else nxt[i]=i+1;
		}
		else
		{
			if(R[i]) nxt[i]=i+1;
			else nxt[i]=i;
		}
	}


	for(int i=N; i>=1; i--)
	{
		if(nxt[i]==i) ans[i]=R[i];
		else ans[i]=ans[i+1];
	}

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

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51