Submission #1066704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066704		Gromp15	Beech Tree (IOI23_beechtree)	C++17	9 / 100	52 ms	15184 KiB

beechtree

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#include "beechtree.h"
using namespace std;

std::vector<int> beechtree(int n, int m, std::vector<int> p, std::vector<int> c)
{
	vector<vector<int>> adj(n);
	for (int i = 1; i < n; i++) adj[p[i]].emplace_back(i);
	bool line = 1;
	for (int i = 1; i < n; i++) line &= p[i] == i-1;
	if (n <= 8) {
		vector<int> ans(n);
		for (int i = 0; i < n; i++) {
			vector<int> cur;
			auto dfs = [&](auto&& s, int v) -> void {
				cur.emplace_back(v);
				for (int u : adj[v]) s(s, u);
			};
			dfs(dfs, i);
			sort(all(cur));
			do {
				if (cur[0] != i) continue;
				map<int, int> cnt;
				bool ok = 1;
				for (int i = 1; i < sz(cur); i++) {
					if (p[cur[i]] != cur[cnt[c[cur[i]]]]) {
						ok = 0; break;
					}
					cnt[c[cur[i]]]++;
				}
				if (ok) {
					ans[i] = 1; break;
				}
			}
			while (next_permutation(all(cur)));
		}
		return ans;
	}
	if (line) {
		vector<int> ans(n);
		int col = -1;
		for (int i = 0; i < n; i++) {
			if (!i) ans[i] = 1;
			else {
				if (!~col) col = c[i];
				else {
					if (col != c[i]) break;
				}
				ans[i] = 1;
			}
		}
		return ans;
	}
}

Compilation message (stderr)

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:9:27: warning: control reaches end of non-void function [-Wreturn-type]
    9 |  vector<vector<int>> adj(n);
      |                           ^

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12