oj.uz

Submission #885025

# Submission time Handle Problem Language Result Execution time Memory
885025 2023-12-08T20:26:10 Z 42kangaroo Beech Tree (IOI23_beechtree) C++17
8 / 100
 168 ms 149148 KB 
//  D. Beech Tree

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

using namespace std;

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

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;
	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, si] = 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);
			}
			if (po[n]) {
				assert(li.size() <= 1);
				if (si > seSi) {
					swap(se, li);
					swap(si, 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]) {
						if (!it.empty()) {
							auto act = itS;
							itS = se.insert(itS, set<pair<int,int>>());
							for (auto cos: it) {
								if (act->erase(cos) == 0) {
									po[n] = false;
									break;
								}
								itS->insert(cos);
							}
						}
					}
				}
			}
		}
	}
	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();
	return {std::move(r), std::move(se), seSi};
}

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 0 ms 348 KB Output is correct
2 Runtime error 1 ms 344 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

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 Runtime error 1 ms 344 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0.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 Runtime error 1 ms 344 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
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 344 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 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
10 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 1 ms 512 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 168 ms 149148 KB Output is correct
6 Correct 157 ms 148952 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 95 ms 21072 KB Output is correct
12 Correct 147 ms 11872 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 Runtime error 1 ms 344 KB Execution killed with signal 6
3 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 1 ms 512 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Runtime error 1 ms 348 KB Execution killed with signal 6
6 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 Runtime error 1 ms 344 KB Execution killed with signal 6
3 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 1 ms 512 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Runtime error 1 ms 348 KB Execution killed with signal 6
6 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 Runtime error 1 ms 344 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -