Submission #640733

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
640733	2022-09-15T07:12:15 Z	ggoh	Toy Train (IOI17_train)	C++14	11 / 100	12 ms	2464 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	2108 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	724 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	2464 KB	Output is correct
2	Correct	8 ms	2332 KB	Output is correct
3	Correct	8 ms	2388 KB	Output is correct
4	Correct	9 ms	2116 KB	Output is correct
5	Correct	8 ms	2112 KB	Output is correct
6	Correct	10 ms	2080 KB	Output is correct
7	Correct	8 ms	1952 KB	Output is correct
8	Correct	9 ms	1948 KB	Output is correct
9	Correct	7 ms	2004 KB	Output is correct
10	Correct	8 ms	2004 KB	Output is correct
11	Correct	10 ms	2004 KB	Output is correct
12	Correct	11 ms	2132 KB	Output is correct
13	Correct	12 ms	2132 KB	Output is correct
14	Correct	9 ms	2116 KB	Output is correct
15	Correct	9 ms	2132 KB	Output is correct
16	Correct	8 ms	2076 KB	Output is correct
17	Correct	8 ms	2100 KB	Output is correct
18	Correct	5 ms	2004 KB	Output is correct