oj.uz

Submission #884517

# Submission time Handle Problem Language Result Execution time Memory
884517 2023-12-07T14:44:21 Z 42kangaroo Beech Tree (IOI23_beechtree) C++17
0 / 100
 1 ms 552 KB 
//  D. Beech Tree

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

using namespace std;

using g_t = vector<vector<int>>;
using dVal = pair<map<int, int>, list<set<int>>>;

struct ValR {
	int d, n, co;
};

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<int>> se;
	se.push_back(set<int>());
	for (auto e: g[n]) {
		if (r.find(c[e]) != r.end()) po[n] = false;
		r[c[e]] = 1;
		ve[c[e]] = {};
		se.back().insert(c[e]);
	}
	for (auto e: g[n]) {
		auto [re, li] = dfs(e, g, po, c);
		if (!po[e]) {
			po[n] = false;
		}
		if (po[n]) {
			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);
			}
			auto itS = se.begin();
			for (auto & it : li) {
				while (itS->size() < it.size()) {
					for (auto cos: *itS) {
						if (it.erase(cos) == 0) {
							po[n] = false;
							break;
						}
					}
					itS++;
				}
				if (!it.empty()) {
					auto act = itS;
					itS = se.insert(itS, set<int>());
					for (auto cos: it) {
						if (act->erase(cos) == 0) {
							po[n] = false;
							break;
						}
						itS->insert(cos);
					}
				}
			}
		}
	}
	if (!po[n]) return {};
	map<int, int> val;
	vector<ValR> si;
	for (auto &[co, vec]: ve) {
		si.push_back({r[co] - 1, 0, co});
		si.push_back({r[co], 0, co});
		for (auto [d, e]: vec) {
			val[e] = 0;
			if (d > r[co]) {
				po[n] = false;
				return {};
			} else if (d == r[co]) {
				si.back().n++;
				si[si.size() - 2].n++;
			} else if (d == r[co] - 1) {
				si[si.size() - 2].n++;
			}
		}
	}
	std::sort(si.begin(), si.end(), [](const ValR &l, const ValR &r) { return l.n > r.n; });
	int i = 1;
	list<set<int>> siO;
	int last = g[n].size() + 1;
	for (auto v: si) {
		for (auto [d, e]: ve[v.co]) {
			if (d >= v.d) {
				if (val[e] != i - 1) {
					po[n] = false;
					return {};
				}
				val[e] = i;
			}
		}
		if (v.d == r[v.co] -1) {
			if (v.n < last) {
				siO.push_back({});
			}
			siO.back().insert(v.co);
			last = v.n;
		}
		i++;
	}
	auto itS = se.begin();
	for (auto & it : siO) {
		while (itS->size() <= it.size()) {
			for (auto cos: *itS) {
				if (it.erase(cos) == 0) {
					po[n] = false;
					break;
				}
			}
			itS++;
		}
		if (!it.empty()) {
			auto act = itS;
			itS = se.insert(itS, set<int>());
			for (auto cos: it) {
				if (act->erase(cos) == 0) {
					po[n] = false;
					break;
				}
				itS->insert(cos);
			}
		}
	}
	return {r, se};
}

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);
	}
	vector<bool> po(N, true);
	dfs(0, g, po, C);
	return {po.begin(), po.end()};
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Incorrect 1 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Incorrect 1 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Incorrect 1 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Incorrect 1 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -