Submission #1233912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233912		MuhammadSaram	Beech Tree (IOI23_beechtree)	C++20	0 / 100	6 ms	14404 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;
vector<pair<int,int>> sub[M];
int dep[M];
bool vis[M];

void dfs(int u)
{
	sub[u].push_back({v[u].size(),u});
	for (int i:nei[u])
	{
		dep[i]=dep[u]+1,dfs(i);
		for (auto p:sub[i])
			sub[u].push_back(p);
	}
	sort(all(sub[u]));
	ans[u]=1;
	for (int c=0;c+1<sub[u].size() && ans[u];c++)
	{
		int i=sub[u][c].second, j=sub[u][c+1].second;
		ans[u]&=ans[i]&ans[j];
		if (dep[i]<dep[j]) ans[u]=0;
		for (int x:v[j]) vis[x]=1;
		for (int x:v[i])
			if (!vis[x]) ans[u]=0;
		for (int x:v[j]) vis[x]=0;
	}
}

vector<int> beechtree(int n, int m, vector<int> p, vector<int> c)
{
	vector<pair<int,int>> ch;
	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