제출 #887010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887010		42kangaroo	Beech Tree (IOI23_beechtree)	C++17	31 / 100	309 ms	160144 KiB

beechtree

//  D. Beech Tree

#include<bits/stdc++.h>
#include "beechtree.h"

using namespace std;

using g_t = vector<vector<int>>;

struct dVal {
	map<int,int> de;
	list<set<pair<int,int>>> se;
	int seSi;
};
vector<int> de;
vector<int> de2;


dVal dfs(int n, g_t &g, vector<bool> &po, vector<int> &c) {
	map<int, int> r;
	map<int, vector<pair<int, int>>> ve;
	list<set<pair<int, int>>> se;
	map<int, map<int,int>>  OmiR;
	int seSi = 0;
	for (auto e: g[n]) {
		if (r.find(c[e]) != r.end()) po[n] = false;
		r[c[e]] = 1;
		ve[c[e]] = {};
	}
	for (auto e: g[n]) {
		auto [re, li, ssi] = dfs(e, g, po, c);
		if (!po[e]) {
			po[n] = false;
		}
		if (!po[n]) continue;
		for (auto &[co, d]: re) {
			if (r.find(co) == r.end()) {
				po[n] = false;
				break;
			}
			if (co == c[e]) r[c[e]] = d + 1;
			ve[co].emplace_back(d, e);
		}
		if (!po[n]) continue;
		if (ssi > seSi) {
			swap(se, li);
			swap(ssi, seSi);
		}
		auto itS = se.begin();
		for (auto &it: li) {
			while (itS != se.end() && itS->size() <= it.size()) {
				for (auto cos: *itS) {
					if (it.erase(cos) == 0) {
						po[n] = false;
						break;
					}
				}
				if (!po[n]) break;
				itS++;
			}
			if (!po[n]) break;
			if (!it.empty()) {
				auto act = se.insert(itS, set<pair<int, int>>());
				for (auto cos: it) {
					if (itS->erase(cos) == 0) {
						po[n] = false;
						break;
					}
					act->insert(cos);
				}
			}
			if (itS->empty()) itS++;
			if (!po[n]) break;
		}
	}
	if (!po[n]) return {};
	se.emplace_back();
	for (auto &[co, vec]: ve) {
		bool dD = true;
		for (auto [d, e]: vec) {
			if (d > r[co]) {
				po[n] = false;
				return {};
			} else if (d == r[co]) {
				dD = false;
				break;
			}
		}
		if (dD) {
			se.back().insert({co, r[co]});
			seSi++;
		}
	}
	if (se.back().empty()) se.pop_back();
	de[n] = seSi;
	return {std::move(r), std::move(se), seSi};
}

pair<array<map<int,map<int,int>>,2>, int> sdfs(int n, g_t& g, vector<bool>& po, vector<int>& c, vector<bool>&vis) {
	if (vis[n]) return {};
	vis[n] = true;
	array<map<int,map<int,int>>,2> res;
	int reSi = 0;
	for (auto e: g[n]) {
		auto [re, si] = sdfs(e, g, po, c,vis);
		if (!po[e]) po[n] = false;
		if (!po[n]) continue;
		re[0][c[e]][de[e]] = re[1][c[e]][de[e]] = de[n];
		si++;
		if (si > reSi) {
			swap(re, res);
			swap(reSi, si);
		}
		for (auto &[co, ma]: re[1]) {
			for (auto &[don, par]: ma) {
				if (res[0][co].upper_bound(don) != res[0][co].end() && res[0][co].upper_bound(don)->second < par) {
					po[n] = false;
					break;
				}
				if (res[1][co].find(don) == res[1][co].end()) reSi++;
				res[1][co][don] = min(res[1][co][don], par);
			}
			if (!po[n]) break;
		}
		if (!po[n]) break;
		for (auto &[co, ma]: re[0]) {
			for (auto &[don, par]: ma) {
				res[0][co][don] = max(res[0][co][don], par);
			}
		}
	}
	return {std::move(res), reSi};
}

void bfs(int n, g_t& g, vector<bool>& vi) {
	int d= 0;
	int pre = -1;
	int preD = de[n];
	priority_queue<tuple<int,int,int>> pq;
	pq.push({de[n], 1, n});
	while (!pq.empty()) {
		auto [dep, pr, t] = pq.top();
		pq.pop();
		if (vi[t]) continue;
		vi[t] = true;
		pr = -pr;
		if (pre != pr || preD != de[t]) d++;
		de2[t] = d;
		pre = pr;
		preD = de[t];
		for (auto e: g[t]) {
			pq.push({de[e], -d, e});
		}
	}
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
	g_t g(N);
	for (int i = 1; i < N; ++i) {
		g[P[i]].push_back(i);
	}
	de = vector<int>(N);
	de2 = vector<int>(N, -1);
	vector<bool> po(N, true);
	dfs(0, g, po, C);
	vector<bool> vis(N, false);
	for (int i = 0; i < N; ++i) {
		if (po[i]) {
			bfs(i, g, vis);
		}
	}
	std::fill(vis.begin(), vis.end(),false);
	for (int i = 0; i < N; ++i) {
		if (po[i]) {
			sdfs(i, g, po, C, vis);
		}
	}
	return {po.begin(), po.end()};
}

#ifndef EVAL
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	vector<int> p(n), c(n);
	for (auto &e: p) {
		cin >> e;
	}
	for (auto &e: c) {
		cin >> e;
	}
	auto res = beechtree(n, m, p, c);
	for (auto e: res) {
		cout << e << " ";
	}
	cout << "\n";
}
#endif

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 5 / 5
• Subtask 3: 9 / 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