oj.uz

Submission #640776

# Submission time Handle Problem Language Result Execution time Memory
640776 2022-09-15T08:08:05 Z ggoh Toy Train (IOI17_train) C++14
22 / 100
 17 ms 2452 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];
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1492 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 852 KB 3rd lines differ - on the 1st 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 2384 KB Output is correct
2 Correct 7 ms 2260 KB Output is correct
3 Correct 8 ms 2260 KB Output is correct
4 Correct 8 ms 2020 KB Output is correct
5 Correct 9 ms 1996 KB Output is correct
6 Correct 11 ms 2004 KB Output is correct
7 Correct 11 ms 1836 KB Output is correct
8 Correct 8 ms 1876 KB Output is correct
9 Correct 8 ms 1876 KB Output is correct
10 Correct 8 ms 1856 KB Output is correct
11 Correct 17 ms 1864 KB Output is correct
12 Correct 9 ms 2004 KB Output is correct
13 Correct 9 ms 1992 KB Output is correct
14 Correct 8 ms 2004 KB Output is correct
15 Correct 8 ms 2004 KB Output is correct
16 Correct 8 ms 1952 KB Output is correct
17 Correct 10 ms 1980 KB Output is correct
18 Correct 6 ms 1916 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1828 KB Output is correct
2 Correct 10 ms 2416 KB Output is correct
3 Correct 10 ms 2452 KB Output is correct
4 Correct 9 ms 2124 KB Output is correct
5 Correct 10 ms 2176 KB Output is correct
6 Correct 11 ms 2260 KB Output is correct
7 Correct 9 ms 2188 KB Output is correct
8 Correct 8 ms 2132 KB Output is correct
9 Correct 8 ms 2132 KB Output is correct
10 Correct 8 ms 2132 KB Output is correct
11 Correct 8 ms 2132 KB Output is correct
12 Correct 9 ms 2132 KB Output is correct
13 Correct 9 ms 2260 KB Output is correct
14 Correct 9 ms 2360 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1860 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 6 ms 1492 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -