Rezultati

Up. imeNalogaJezikRezultatČas oddaje
ctrl-alt-defeat-2019 Barvanje drevesa C++ 0/100Napačen odgovor (WA) 24. apr '19 @ 18:10

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 3,316 MiB 0,000 s OK
#2 [več] 10/10 3,219 MiB 0,000 s OK
#3 [več] 10/10 3,191 MiB 0,004 s OK
#4 [več] 10/10 3,227 MiB 0,004 s OK
#5 [več] 0/10 3,316 MiB 0,000 s Napačen odgovor
#6 [več] 0/10 3,363 MiB 0,000 s Napačen odgovor
#7 [več] 0/10 3,363 MiB 0,010 s Napačen odgovor
#8 [več] 0/10 3,363 MiB 0,004 s Napačen odgovor
#9 [več] 10/10 3,277 MiB 0,000 s OK
#10 [več] 0/10 3,367 MiB 0,004 s Napačen odgovor

Ocenjevani program (Barvanje.cpp):
#include <bits/stdc++.h>

using namespace std;

int last(int a,int b)
{
	vector<bool> vis(4,0);
	vis[a]=1;
	vis[b]=1;
	for(int i=1;i<=3;i++) if(!vis[i]) return i;
}

int main()
{
	int n;
	scanf("%d",&n);
	vector<int> v[n+1]; //Children
	vector<bool> isChild(n+1,0);
	int m=0;
	for(int i=1;i<=n;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		isChild[a]=1;
		isChild[b]=1;
		if(a!=0) v[i].push_back(a);
		if(b!=0) v[i].push_back(b);
		m=max(m,(int)v[i].size());
	}
	int root;
	for(int i=1;i<=n;i++)
	{
		if(!isChild[i])
		{
			root=i;
			break;
		}
	}
	vector<int> res(n+1,0);
	if(n==1) res[1]=1;
	else if(m==1)
	{
		res[root]=1;
		int now=root;
		int color=2;
		while(v[now].size()!=0)
		{
			res[v[now][0]]=color;
			color=3-color;
			now=v[now][0];
		}
	}
	else
	{
		vector<int> now,next;
		res[root]=1;
		now.push_back(root);
		while(now.size()!=0)
		{
			for(int i=0;i<(int)now.size();i++)
			{
				int e=now[i];
				if(v[e].size()==1)
				{
					if(i!=(int)now.size()-1) res[v[e][0]]=last(res[now[i+1]],res[e]);
					else res[v[e][0]]=last(res[e],0);
					if(v[v[e][0]].size()!=0) next.push_back(v[e][0]);
				}
				else
				{
					if(i!=(int)now.size()-1) res[v[e][1]]=last(res[now[i+1]],res[e]);
					else res[v[e][1]]=last(res[e],0);
					res[v[e][0]]=last(res[e],res[v[e][1]]);
					if(v[v[e][0]].size()!=0) next.push_back(v[e][0]);
					if(v[v[e][1]].size()!=0) next.push_back(v[e][1]);
				}
			}
			now=next;
			next.clear();
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",res[i]);
	printf("\n");
	return 0;
}