oj.uz

Submission #640768

# Submission time Handle Problem Language Result Execution time Memory
640768 2022-09-15T08:02:27 Z ggoh Toy Train (IOI17_train) C++14
11 / 100
 12 ms 2612 KB 
#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];
 
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);
	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(!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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2612 KB Output is correct
2 Correct 8 ms 2388 KB Output is correct
3 Correct 7 ms 2392 KB Output is correct
4 Incorrect 9 ms 2076 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1876 KB Output is correct
2 Correct 8 ms 2452 KB Output is correct
3 Correct 11 ms 2544 KB Output is correct
4 Correct 8 ms 2200 KB Output is correct
5 Correct 8 ms 2320 KB Output is correct
6 Correct 8 ms 2312 KB Output is correct
7 Correct 9 ms 2328 KB Output is correct
8 Correct 12 ms 2196 KB Output is correct
9 Correct 8 ms 2316 KB Output is correct
10 Correct 8 ms 2216 KB Output is correct
11 Correct 8 ms 2260 KB Output is correct
12 Correct 9 ms 2200 KB Output is correct
13 Correct 9 ms 2388 KB Output is correct
14 Correct 9 ms 2432 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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