Submission #879417

#	Time	Username	Problem	Language	Result	Execution time	Memory
879417		SanguineChameleon	Beech Tree (IOI23_beechtree)	C++17	100 / 100	509 ms	118868 KiB

beechtree

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

vector<set<pair<int, int>>> S;
vector<map<int, int>> ch;
vector<int> sz;
vector<int> res;

bool check(int u, int v) {
	for (auto [c, x]: ch[u]) {
		auto it = ch[v].find(c);
		if (it == ch[v].end()) {
			return false;
		}
		if (sz[x] > sz[it->second]) {
			return false;
		}
	}
	return true;
}

void calc(int u) {
	if (res[u] == 0) {
		return;
	}
	sz[u] = 1;
	for (auto [c, v]: ch[u]) {
		if (res[v] == 0) {
			res[u] = 0;
			return;
		}
		sz[u] += sz[v];
	}
	S[u].emplace(sz[u], u);
	for (auto [c, v]: ch[u]) {
		if (S[u].size() < S[v].size()) {
			S[u].swap(S[v]);
		}
		for (auto p: S[v]) {
			auto it = S[u].insert(p).first;
			if (it != S[u].begin() && !check(prev(it)->second, p.second)) {
				res[u] = 0;
				return;
			}
			if (next(it) != S[u].end() && !check(p.second, next(it)->second)) {
				res[u] = 0;
				return;
			}
		}
	}
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
	S.resize(N);
	ch.resize(N);
	sz.resize(N);
	res.resize(N, 1);
	for (int i = 1; i < N; i++) {
		if (res[P[i]] == 0) {
			continue;
		}
		auto it = ch[P[i]].find(C[i]);
		if (it != ch[P[i]].end()) {
			res[P[i]] = 0;
		}
		else {
			ch[P[i]][C[i]] = i;
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		calc(i);
	}
	return res;
}

• 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