Submission #879414

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
879414	2023-11-27T10:32:20 Z	SanguineChameleon	Beech Tree (IOI23_beechtree)	C++17	5 / 100	137 ms	80164 KB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;

vector<set<pair<int, int>>> S;
vector<map<int, int>> ch;
vector<int> sz;
vector<int> res;

bool check(int u, int v) {
	for (auto [c, x]: ch[u]) {
		auto it = ch[v].find(c);
		if (it == ch[v].end()) {
			return false;
		}
		if (sz[x] > sz[it->second]) {
			return false;
		}
	}
	return true;
}

void dfs(int u) {
	if (res[u] == 0) {
		return;
	}
	sz[u] = 1;
	for (auto [c, v]: ch[u]) {
		dfs(v);
		if (res[v] == 0) {
			res[u] = 0;
			return;
		}
		sz[u] += sz[v];
	}
	S[u].emplace(sz[u], u);
	for (auto [c, v]: ch[u]) {
		if (S[u].size() < S[v].size()) {
			S[u].swap(S[v]);
		}
		for (auto p: S[v]) {
			auto it = S[u].insert(p).first;
			if (it != S[u].begin() && !check(prev(it)->second, p.second)) {
				res[u] = 0;
				return;
			}
			if (next(it) != S[u].end() && !check(p.second, next(it)->second)) {
				res[u] = 0;
				return;
			}
		}
	}
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
	S.resize(N);
	ch.resize(N);
	sz.resize(N);
	res.resize(N, 1);
	for (int i = 1; i < N; i++) {
		if (res[P[i]] == 0) {
			continue;
		}
		auto it = ch[P[i]].find(C[i]);
		if (it != ch[P[i]].end()) {
			res[P[i]] = 0;
		}
		else {
			ch[P[i]][C[i]] = i;
		}
	}
	dfs(0);
	int cut = -1;
	for (int i = 0; i < N; i++) {
		if (res[i] == 1) {
			cut = i;
			break;
		}
	}
	if (cut != -1) {
		for (int i = cut; i < N; i++) {
			assert(res[i] == 1);
		}
	}
	return res;
}

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Runtime error	1 ms	604 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	Correct	0 ms	352 KB	Output is correct
4	Correct	0 ms	352 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	1 ms	348 KB	Output is correct
11	Correct	1 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	352 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	0 ms	440 KB	Output is correct
19	Correct	0 ms	352 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	440 KB	Output is correct
22	Incorrect	0 ms	352 KB	2nd lines differ - on the 2nd token, expected: '0', found: '1'
23	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	352 KB	Output is correct
4	Correct	0 ms	352 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	83 ms	61628 KB	Output is correct
8	Correct	85 ms	61648 KB	Output is correct
9	Correct	1 ms	360 KB	Output is correct
10	Correct	0 ms	356 KB	Output is correct
11	Correct	0 ms	448 KB	Output is correct
12	Correct	0 ms	360 KB	Output is correct
13	Correct	2 ms	960 KB	Output is correct
14	Correct	1 ms	1116 KB	Output is correct
15	Correct	1 ms	988 KB	Output is correct
16	Correct	2 ms	860 KB	Output is correct
17	Correct	137 ms	80164 KB	Output is correct
18	Correct	116 ms	73800 KB	Output is correct
19	Correct	93 ms	64596 KB	Output is correct
20	Correct	83 ms	61524 KB	Output is correct

Subtask #3
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Runtime error	1 ms	644 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #4
0.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	83 ms	61628 KB	Output is correct
6	Correct	85 ms	61648 KB	Output is correct
7	Runtime error	1 ms	604 KB	Execution killed with signal 6
8	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Runtime error	1 ms	604 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	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	1 ms	348 KB	Output is correct
7	Correct	1 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	352 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	440 KB	Output is correct
15	Correct	0 ms	352 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	440 KB	Output is correct
18	Incorrect	0 ms	352 KB	2nd lines differ - on the 2nd token, expected: '0', found: '1'
19	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Runtime error	1 ms	604 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	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	1 ms	348 KB	Output is correct
7	Correct	1 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	352 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	440 KB	Output is correct
15	Correct	0 ms	352 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	440 KB	Output is correct
18	Incorrect	0 ms	352 KB	2nd lines differ - on the 2nd token, expected: '0', found: '1'
19	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Runtime error	1 ms	604 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Submission #879414

Compilation message