Submission #1233895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233895		MuhammadSaram	Beech Tree (IOI23_beechtree)	C++17	0 / 100	5 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;

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]=2;
	if (nei[u].size()!=v[u].size()) ans[u]=0;
	if (cnt>1) return;
	set<int> se;
	for (int i:v[u]) se.insert(i);
	for (int i:nei[u])
	{
		if (v[i].empty()) continue;
		ans[u]=ans[i]-1;
		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);
	for (int i=0;i<n;i++)
		ans[i]=max(ans[i],0),ans[i]=min(ans[i],1);
	
	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