oj.uz

Submission #884177

# Submission time Handle Problem Language Result Execution time Memory
884177 2023-12-06T16:45:14 Z 42kangaroo Beech Tree (IOI23_beechtree) C++17
17 / 100
 2000 ms 124216 KB 
//  D. Beech Tree

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

using namespace std;

using g_t = vector<vector<int>>;
using dVal = map<int, int>;

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

dVal dfs(int n, g_t &g, vector<bool>& po, vector<int>& c) {
	dVal r;
	map<int, vector<pair<int,int>>> ve;
	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]) {
		dVal re = 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].push_back({d, e});
			}
		}
	}
	if (!po[n]) return {};
	map<int,int> val;
	vector<ValR> si;
	for (auto &[co, vec]: ve) {
		for (int i = 1; i <= r[co]; ++i) {
			si.push_back({i, 0, co});
			for (auto [d, e]: vec) {
				val[e] = 0;
				if (d > r[co]) {
					po[n] = false;
					return {};
				} else if (d >= i) {
					si.back().n++;
				}
			}
		}
	}
	std::sort(si.begin(), si.end(), [](const ValR& l, const ValR& r) {return l.n > r.n;});
	int i = 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;
			}
		}
		i++;
	}
	return r;
}

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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 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 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 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
15 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 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 150 ms 124216 KB Output is correct
8 Correct 145 ms 124116 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 54 ms 1644 KB Output is correct
14 Correct 25 ms 1660 KB Output is correct
15 Correct 3 ms 1628 KB Output is correct
16 Correct 2 ms 1628 KB Output is correct
17 Execution timed out 2101 ms 124024 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 92 ms 6372 KB Output is correct
16 Correct 63 ms 5184 KB Output is correct
17 Correct 78 ms 5356 KB Output is correct
18 Correct 94 ms 6228 KB Output is correct

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 348 KB Output is correct
5 Correct 150 ms 124216 KB Output is correct
6 Correct 145 ms 124116 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 93 ms 18260 KB Output is correct
12 Correct 153 ms 11596 KB Output is correct

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 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 348 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 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 0 ms 344 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 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 0 ms 344 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 1 ms 344 KB Output is correct
2 Correct 0 ms 344 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 348 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 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 0 ms 344 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 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 0 ms 344 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 1 ms 344 KB Output is correct
2 Correct 0 ms 344 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 348 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 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -