Submission #411197

#	Time	Username	Problem	Language	Result	Execution time	Memory
411197		Jasiekstrz	Toy Train (IOI17_train)	C++17	23 / 100	1796 ms	149796 KiB

train

#include<bits/stdc++.h>
#include "train.h"
using namespace std;
const int N=5e3;
bool ab[N+10];
bool charge[N+10];
int deg[N+10];
vector<int> e[N+10];
int vis[N+10];
vector<int> f[N+10];
bool loop[N+10];
void dfs(int x,int c)
{
	f[x].push_back(c);
	for(auto v:e[x])
	{
		vis[v]--;
		if(vis[v]==0)
		{
			if(v==c)
				loop[c]=true;
			else
				dfs(v,c);
		}
	}
	return;
}
vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v)
{
	int n=a.size(),m=u.size();
	for(int i=0;i<n;i++)
	{
		ab[i]=a[i];
		charge[i]=r[i];
	}
	for(int i=0;i<m;i++)
	{
		e[v[i]].push_back(u[i]);
		deg[u[i]]++;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			vis[j]=(ab[j] ? 1:deg[j]);
		dfs(i,i);
	}
	vector<int> ans(n);
	for(int i=0;i<n;i++)
	{
		ans[i]=0;
		for(auto ch:f[i])
		{
			if(charge[ch] && loop[ch])
			{
				ans[i]=1;
				break;
			}
		}
	}
	return ans;
}

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