Submission #1071204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071204		Muhammad_Aneeq	Beech Tree (IOI23_beechtree)	C++17	14 / 100	2099 ms	19932 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]={};
bool check(vector<int>d,int u)
{
	for (auto i:d)
		ind[i]=-1,cnt[c[i]]=0;
	int z=1;
	for (auto i:d)
	{
		if (ind[p[i]]==-1)
			return 0;
		if (cnt[c[i]]!=ind[p[i]])
			return 0;
		ind[i]=z++;
		cnt[c[i]]++;
	}
	return 1;
}
vector<int> dfs(int u)
{
	vector<int>d;
	bool w=1;
	set<int>s;
	for (auto i:nei[u])
	{
		s.insert(c[i]);
		h[i]=h[u]+1;
		vector<int>f=dfs(i);
		for (auto i:f)
			d.push_back(i);
		w&=ans[i];
	}
	if (s.size()!=nei[u].size())
		w=0;
	if (w==0)
	{
		ans[u]=0;
		return {};
	}
	sort(begin(d),end(d));
	while (!check(d,u))
	{
		if (!next_permutation(begin(d),end(d)))
		{
			ans[u]=0;
			break;
		}
	}
	d.push_back(u);
	return d;
}
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],ans[i]=1;
	bool w=1;
	for (int i=1;i<N;i++)
	{
		nei[P[i]].push_back(i);
		if (P[i]!=i-1)
			w=0;
	}
	if (w)
	{
		vector<int>ans(N,0);
		ans[N-1]=1;
		for (int i=N-2;i>=0;i--)
		{
			if (c[i+1]==c[N-1])
				ans[i]=1;
			else
				break;
		}
		return ans;
	}
	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: 9 / 9
• Subtask 2: 5 / 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