Submission #1233902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233902		MuhammadSaram	Beech Tree (IOI23_beechtree)	C++20	0 / 100	4 ms	9800 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()

const int M = 2e5 + 1;

vector<int> nei[M],v[M],ans;
bool b[M];

void dfs(int u)
{
	if (nei[u].empty()) ans[u]=1;
	int cnt=0;
	for (int i:nei[u])
		dfs(i),cnt+=!nei[i].empty();
	if (!cnt) ans[u]=b[u]=1;
	if (nei[u].size()!=v[u].size())
	{
		ans[u]=0;
		return;
	}
	if (cnt>1) return;
	set<int> se;
	for (int i:v[u]) se.insert(i);
	for (int i:nei[u])
	{
		if (v[i].empty() or !b[i]) continue;
		ans[u]=ans[i];
		for (int j:v[i])
			if (!se.count(j)) ans[u]=0;
	}
}

vector<int> beechtree(int n, int m, vector<int> p, vector<int> c)
{
	for (int i=n-1;i>0;i--)
	{
		nei[p[i]].push_back(i),v[p[i]].push_back(c[i]);
		sort(all(v[i])),v[i].resize(unique(all(v[i]))-begin(v[i]));
	}
	ans=vector<int>(n);
	dfs(0);
	
	return ans;
}

• 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