Submission #2936856


Source Code Expand

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

void Read(int &p)
{
	p=0;
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9')
		p=p*10+c-'0',c=getchar();
}

const int MAXN=102018;
int N,k,root,u,v,val[MAXN],eoro[MAXN];
bool vis[MAXN],ol[MAXN];
vector<int> G[MAXN];
vector<int> C[MAXN];

bool build_tree(int p)
{
	vis[p]=1;
	for(unsigned int i=0;i<G[p].size();i++)
	{
		int t=G[p][i];
		if(!vis[t])
		{
			C[p].push_back(t);
			if(eoro[t]!=-1 && eoro[t]==eoro[p]) return 1;
			eoro[t]=(eoro[p]+1)%2;
			bool o=build_tree(t);
			if(o) return 1;
		}
	}
	return 0;
}


bool ed;
void draw(int p)
{
	if(ed) return;
	if(C[p].size()==0)
	{
		bool cnt=0;
		for(int i=1;i<=N && !cnt;i++)
			if(val[i]==-1) cnt=1;
		
		if(!cnt)
		{
			for(int i=1;i<=N;i++)
				printf("%d\n",val[i]);
			ed=1;
		}
		return ;
	}
	for(unsigned int i=0;i<C[p].size() && !ed;i++)
	{
		int t=C[p][i];
		if(ol[t]) 
		{ 
			if(val[t]-val[p]>1 || val[p]-val[t]>1)
			{
				if(ol[p]) ed=1,puts("No");
				return ;
			}
			else draw(t);
			continue;
		}
		val[t]=val[p]+1,draw(t);
		if(val[t]>=1) val[t]=val[p]-1,draw(t);
	}
	if(ed) return ;
}

int main()
{
	memset(eoro,-1,sizeof eoro);
	memset(val,-1,sizeof val);
	Read(N);
	for(int i=2;i<=N;i++)
		Read(u),Read(v),G[u].push_back(v),G[v].push_back(u);
	
	Read(k);
	Read(root),Read(val[root]),eoro[root]=val[root]%2,ol[root]=1;
	for(int i=2;i<=k;i++)
		Read(u),Read(v),val[u]=v,eoro[u]=v%2,ol[u]=1;
	
	if(build_tree(root)) ed=1,puts("No");
	else draw(root);
	if(!ed) puts("No");
}

Submission Info

Submission Time
Task C - 1D Reversi
User Crloss
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1673 Byte
Status TLE
Exec Time 2103 ms
Memory 5760 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 300
Status
TLE × 3
TLE × 15
Set Name Test Cases
sample sample_01.txt, sample_02.txt, sample_03.txt
All alternate_01.txt, alternate_02.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, same_01.txt, same_02.txt, sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, small_03.txt
Case Name Status Exec Time Memory
alternate_01.txt TLE 2103 ms 5760 KB
alternate_02.txt TLE 2103 ms 5760 KB
random_01.txt TLE 2103 ms 5760 KB
random_02.txt TLE 2103 ms 5760 KB
random_03.txt TLE 2103 ms 5760 KB
random_04.txt TLE 2103 ms 5760 KB
random_05.txt TLE 2103 ms 5760 KB
same_01.txt TLE 2103 ms 5760 KB
same_02.txt TLE 2103 ms 5760 KB
sample_01.txt TLE 2103 ms 5760 KB
sample_02.txt TLE 2103 ms 5760 KB
sample_03.txt TLE 2103 ms 5760 KB
small_01.txt TLE 2103 ms 5760 KB
small_02.txt TLE 2103 ms 5760 KB
small_03.txt TLE 2103 ms 5760 KB