Submission #640733

#	Time	Username	Problem	Language	Result	Execution time	Memory
640733		ggoh	Toy Train (IOI17_train)	C++14	11 / 100	12 ms	2464 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],go[5005],self[5005],C[5005];
vector<int>G[5005],rev[5005],SCC[5005],E[5005];
int v[5005],st[5005],ind[5005],sz,col,D[5005];

void dfs1(int p)
{
	v[p]=1;
	for(auto &k:G[p])
	{
		if(!v[k])dfs1(k);
	}
	st[sz++]=p;
}
void dfs2(int p)
{
	v[p]=1;
	SCC[sz].push_back(p);
	go[p]=sz;
	for(auto &k:rev[p])
	{
		if(!v[k])dfs2(k);
	}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> uu, vector<int> vv) {
	n=sz(a);
	m=sz(uu);
	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++)
	{
		if(uu[i]==vv[i])
		{
			self[uu[i]]=1;
			continue;
		}
		G[uu[i]].push_back(vv[i]);
		rev[vv[i]].push_back(uu[i]);
	}
	sz=0;
	memset(v,0,sizeof(v));
	for(int i=0;i<n;i++)if(!v[i])dfs1(i);
	memset(v,0,sizeof(v));
	sz=0;
	for(int i=n-1;i>=0;i--)
	{
		if(!v[st[i]])
		{
			sz++;
			dfs2(st[i]);
		}
	}
	for(int i=1;i<=sz;i++)
	{
		if(sz(SCC[i])==1)
		{
			if(self[SCC[i][0]]==1 && R[SCC[i][0]])C[i]=1;
		}
		else
		{
			for(auto &k:SCC[i])
			{
				if(R[k])C[i]=1;
			}
		}
	}
	for(int i=0;i<m;i++)
	{
		if(go[uu[i]]!=go[vv[i]])
		{
			E[go[uu[i]]].push_back(go[vv[i]]);
			ind[go[vv[i]]]++;
		}
	}
	queue<int>P;
	for(int i=1;i<=sz;i++)
	{
		if(ind[i]==0)P.push(i);
	}
	vector<int>dag;
	while(!P.empty())
	{
		int p=P.front();P.pop();
		dag.push_back(p);
		for(auto &k:E[p])
		{
			ind[k]--;
			if(ind[k]==0)P.push(k);
		}
	}
	for(int i=sz(dag)-1;i>=0;i--)
	{
		if(C[dag[i]]==1)D[dag[i]]=1;
		else
		{
			for(auto &k:E[dag[i]])
			{
				if(D[k]==1)D[dag[i]]=1;
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		res[i]=D[go[i]];
	}
	return res;
}

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