Submission #884507

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884507	2023-12-07T14:18:31 Z	42kangaroo	Beech Tree (IOI23_beechtree)	C++17	13 / 100	282 ms	192340 KB

beechtree

//  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, {});
					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 = -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]) {
			if (v.n > last) {
				siO.push_front({});
			}
			siO.front().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, {});
			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	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	436 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #1
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	432 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	436 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Incorrect	1 ms	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
15	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	432 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	213 ms	192152 KB	Output is correct
8	Correct	206 ms	192340 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	432 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	3 ms	2140 KB	Output is correct
14	Correct	3 ms	2140 KB	Output is correct
15	Correct	2 ms	2344 KB	Output is correct
16	Correct	2 ms	2140 KB	Output is correct
17	Correct	277 ms	192108 KB	Output is correct
18	Correct	282 ms	192316 KB	Output is correct
19	Correct	219 ms	192336 KB	Output is correct
20	Correct	209 ms	192340 KB	Output is correct

Subtask #3
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	432 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	2 ms	348 KB	Output is correct
14	Correct	2 ms	348 KB	Output is correct
15	Correct	167 ms	7508 KB	Output is correct
16	Correct	131 ms	6228 KB	Output is correct
17	Runtime error	29 ms	11088 KB	Execution killed with signal 11
18	Halted	0 ms	0 KB	-

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	436 KB	Output is correct
5	Correct	213 ms	192152 KB	Output is correct
6	Correct	206 ms	192340 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	2 ms	448 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	143 ms	25880 KB	Output is correct
12	Correct	250 ms	14956 KB	Output is correct

Subtask #5
0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	432 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	436 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Incorrect	1 ms	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
18	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	436 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Incorrect	1 ms	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
11	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	432 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	436 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Incorrect	1 ms	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
18	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	436 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Incorrect	1 ms	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
11	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	432 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	436 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Incorrect	1 ms	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
18	Halted	0 ms	0 KB	-

Submission #884507

Compilation message