Submission #1229924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229924		PlayVoltz	Beech Tree (IOI23_beechtree)	C++20	100 / 100	438 ms	125024 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

vector<map<int, int> > m;
vector<int> sz, ans;
vector<set<pii> > s;
vector<vector<pii> > graph;

void dfs(int node){
	sz[node]=1;
	set<int> temp;
	for (auto num:graph[node])dfs(num.fi), sz[node]+=sz[num.fi], temp.insert(num.se), ans[node]&=ans[num.fi];
	if (temp.size()!=graph[node].size())ans[node]=0;
	s[node].insert(mp(sz[node], node));
	for (auto num:graph[node]){
		if (s[node].size()<s[num.fi].size())swap(s[node], s[num.fi]);
		for (auto a:s[num.fi]){
			s[node].insert(a);
			auto it = s[node].find(a);
			if (it!=s[node].begin()){
				--it;
				for (auto c:m[it->se])if (!m[a.se].count(c.fi)||sz[c.se]>sz[m[a.se][c.fi]])ans[node]=0;
				++it;
			}
			++it;
			if (it!=s[node].end())for (auto c:m[a.se])if (!m[it->se].count(c.fi)||sz[c.se]>sz[m[it->se][c.fi]])ans[node]=0;
		}
	}
}

vector<int> beechtree(int n, int M, vector<int> p, vector<int> c){
	graph.clear();
	ans.clear();
	sz.clear();
	m.clear();
	s.clear();
	s.resize(n);
	m.resize(n);
	ans.resize(n, 1);
	sz.resize(n);
	graph.resize(n);
	for (int i=1; i<n; ++i)graph[p[i]].pb(mp(i, c[i])), m[p[i]][c[i]]=i;
	dfs(0);
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 12 / 12
• Subtask 8: 17 / 17
• Subtask 9: 12 / 12