Submission #640651

#	Time	Username	Problem	Language	Result	Execution time	Memory
640651		ggoh	Toy Train (IOI17_train)	C++14	5 / 100	8 ms	1432 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int>pii;

int n,m,R[5005],A[5005];
vector<int>G[5005];
int D[5005];

int f(int p)
{
	if(D[p]>=0)return D[p];
	if(sz(G[p])==1)
	{
		if(G[p][0]==p)
		{
			if(R[p])return D[p]=1;
			else return D[p]=0;
		}
		else
		{
			return D[p]=f(p+1);
		}
	}
	else
	{
		if(A[p])
		{
			if(R[p])return D[p]=1;
			else return D[p]=f(p+1);
		}
		else
		{
			if(R[p])return D[p]=f(p+1);
			else return D[p]=0;
		}
	}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n=sz(a);
	m=sz(u);
	vector<int> res(n);
	for(int i=0;i<n;i++)
	{
		A[i]=a[i];
		R[i]=r[i];
	}
	for(int i=0;i<m;i++)G[u[i]].push_back(v[i]);
	memset(D,-1,sizeof(D));
	for(int i=0;i<n;i++)
	{
		res[i]=f(i);
	}

	return res;
}

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