Submission #1233966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233966		MuhammadSaram	Beech Tree (IOI23_beechtree)	C++20	8 / 100	78 ms	58184 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)
{
	int cnt=0,x;
	for (int i:nei[u])
	{
		if (nei[i].size()) cnt++,x=i;
		dfs(i);
	}
	if (!cnt) ans[u]=b[u]=1;
	set<int> se;
	for (int i:v[u]) se.insert(i);
	if (se.size()!=v[u].size())
	{
		ans[u]=0;
		return;
	}
	if (cnt!=1 or !b[x] or !ans[x]) return;
	ans[u]=1;
	for (int i:v[x])
		if (!se.count(i)) 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]);
	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: 8 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12