Submission #1202088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202088		randnt93	September (APIO24_september)	C++20	0 / 100	1 ms	324 KiB

september

#include "september.h"

#include <algorithm>
#include <iostream>
#include <climits>
#include <bitset>
#include <vector>
#include <set>

int dfs(std::vector<int>& F, std::set<int>& leafs, int* depth, int n) {
	if (depth[n] != INT_MAX) return depth[n];
	if (F[n] == -1) return 0;

	auto parent = leafs.find(F[n]);
	if (parent != leafs.end())
		leafs.erase(parent);

	depth[n] = dfs(F, leafs, depth, F[n]) + 1;
	return depth[n];
}

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	std::set<int> leafs;
	int depth[N];
	for (int x = 0; x < N; x++)
		depth[x] = INT_MAX, leafs.insert(x);

	for (int x = 1; x < N; x++)
		dfs(F, leafs, depth, x);

	std::bitset<100005> rem;
	int days = 0;

	bool bad = 0;
	for (auto record: S) {
		std::sort(record.begin(), record.end(), [&] (int a, int b) {
		  if (depth[a] == depth[b]) return a > b;
		  return depth[a] > depth[b];
		});

		bool g = 1;
		for (int lf: record) {
			auto leaf = leafs.find(lf);
			if (leaf == leafs.end() || rem[lf]) {
				g = 0;
				break;
			}

			if (F[lf] != -1)
				leafs.insert(F[lf]);
			N--;
			leafs.erase(leaf);
			rem[lf] = 1;
		}

		if (!g) {
			bad = 1;
			break;
		}
		days++;
	}

	if (!bad) return days + N;
	return days;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 5
• Subtask 4: 0 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16