Submission #640776

#	Time	Username	Problem	Language	Result	Execution time	Memory
640776		ggoh	Toy Train (IOI17_train)	C++14	22 / 100	17 ms	2452 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],ch[5005];
vector<int>G[5005],rev[5005],SCC[5005],SCCX[5005],E[5005];
int v[5005],st[5005],ind[5005],sz,col,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;
		}
	}
}
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);
	}
}
 
void dfsx1(int p)
{
	v[p]=1;
	for(auto &k:G[p])
	{
		if(!R[k] && !v[k])dfsx1(k);
	}
	st[sz++]=p;
}
void dfsx2(int p)
{
	v[p]=1;
	SCCX[sz].push_back(p);
	for(auto &k:rev[p])
	{
		if(!R[k] && !v[k])dfsx2(k);
	}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> uu, vector<int> vv) {
	n=sz(a);
	m=sz(uu);
   int T=0;
	vector<int> res(n);
	for(int i=0;i<n;i++)
	{
		A[i]=a[i];
		R[i]=r[i];
      	if(a[i]==1)T++;
	}
	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]);
	}
  if(T!=n && T!=0){
	for(int i=0;i<m;i++)G[uu[i]].push_back(vv[i]);
	memset(D,-1,sizeof(D));
	for(int i=0;i<n;i++)
	{
		res[i]=f(i);
	}
  }
  else if(T==n)
  {
    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]];
	}
  }
  else
  {
 
	sz=0;
	memset(v,0,sizeof(v));
	for(int i=0;i<n;i++)
	{
		if(!R[i] && !v[i])dfsx1(i);
	}
	memset(v,0,sizeof(v));
	int o=sz;
	sz=0;
	for(int i=o-1;i>=0;i--)
	{
		if(!v[st[i]])
		{
			sz++;
			dfsx2(st[i]);
		}
	}
	for(int i=1;i<=sz;i++)
	{
		if(sz(SCCX[i])==1)
		{
			if(self[SCCX[i][0]]==1)ch[SCCX[i][0]]=1;
			continue;
		}
		for(auto &k:SCCX[i])
		{
			ch[k]=1;
		}
	}
 
	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++)
	{
		for(auto &k:SCC[i])
		{
			if(ch[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]=1-D[go[i]];
	}
  }
	return res;
}

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