Submission #1202666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202666		randnt93	September (APIO24_september)	C++20	0 / 100	1093 ms	320 KiB

september

#include "september.h"

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <climits>
#include <bitset>
#include <vector>
#include <queue>
#include <set>

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

	childs[F[n]].insert(n);
	childc[F[n]]++;

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

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

void add_needed(std::set<int>* childs, std::bitset<100005>& rem, int n, std::set<int>& target) {
	for (int c: childs[n]) {
		if (rem[c]) continue;
		rem[c] = 1;
		target.insert(c);
		add_needed(childs, rem, n, target);
	}
}

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

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

	int days = 0,
		timer = 0,
		topday = 0;
	std::priority_queue<
		pt,
		std::vector<pt>,
		std::greater<pt>
	> parsed;

	for (int x = 0; x < M; x++)
		parsed.push({{0, timer++}, x});

	std::bitset<100005> trem;
	std::set<int> target, repls[N];
	while (parsed.top().first.first < (N - 1)) {
		auto p = parsed.top(); parsed.pop();
		// std::cout << "Member: " << p.second << "\n";
		if (topday == p.first.first) {
			int leaf = S[p.second][topday++];
			target.insert(leaf);
			if (childc[leaf] > 0) {
				add_needed(childs, trem, leaf, target);
				if (F[leaf] != -1)
					childc[F[leaf]]--;
			}

			days++;
		}

		int tsize = target.size();
		while (1) {
			while (repls[p.second].size() < target.size())
				repls[p.second].insert(S[p.second][p.first.first++]);

			if (repls[p.second] != target) {
				for (int v: repls[p.second]) {
					if (target.find(v) != target.end())
						continue;

					if (childc[v] > 0) {
						add_needed(childs, trem, v, target);
						if (F[v] != -1)
							childc[F[v]]--;
					}

					trem[v] = 1;
					target.insert(v);
				}
				continue;
			} break;
		}

		// std::cout << "target: ";
		// for (int a: target)
		// 	std::cout << " " << a;
		// std::cout << "\n";
		parsed.push({{target.size(), timer++}, p.second});
	}

	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