Submission #1071050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071050		Muhammad_Aneeq	Beech Tree (IOI23_beechtree)	C++17	0 / 100	2 ms	9660 KiB

beechtree

#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
int const MAXN=2e5+10;
vector<int>nei[MAXN]={};
int c[MAXN]={};
int h[MAXN]={};
int ans[MAXN]={};
int ind[MAXN]={};
int cnt[MAXN]={};
int p[MAXN]={};
vector<int> dfs(int u)
{
	set<pair<int,int>>d;
	for (auto i:nei[u])
	{
		h[i]=h[u]+1;
		vector<int>f=dfs(i);
		for (auto i:f)
		{
			ind[i]=-1;
			cnt[c[i]]=0;
			d.insert({h[i],i});
		}
	}
	int z=1;
	ind[u]=0;
	while (d.size())
	{
		int x=-1;
		for (auto i:d)
		{
			int v=i.second;
			if (ind[p[v]]!=-1&&cnt[c[v]]==ind[p[v]])
			{
				x=v;
				break;
			}
		}	
		if (x==-1)
			break;
		d.erase({h[x],x});
		cnt[c[x]]++;
		ind[x]=z++;
	}
	ans[u]=(d.size()==0);
	vector<int>qw;
	qw.push_back(u);
	for (auto i:d)
		qw.push_back(i.second);
	return qw;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
	for (int i=0;i<N;i++)
		c[i]=C[i],p[i]=P[i];
	for (int i=1;i<N;i++)
		nei[P[i]].push_back(i);
	dfs(0);
	vector<int>d;
	for (int i=0;i<N;i++)
		d.push_back(ans[i]);
	return d;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12