Submission #1203264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203264		randnt93	September (APIO24_september)	C++20	100 / 100	120 ms	10704 KiB

september

#include "september.h"

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

#define bset std::bitset<100005>
using namespace std;

void dfs(bset& S, vector<int>& P, int N, vector<vector<int>>& O) {
	if (S[N]) return;
	S[N] = 1;
	if (P[N] != -1)
		O[P[N]].push_back(N), dfs(S, P, P[N], O);
}

void add_childs(vector<vector<int>>& C, int N, bset& target, bset& rem, int& top) {
	++top;
	target[N] = 1;
	for (int c: C[N]) {
		if (target[c]) continue;
		add_childs(C, c, target, rem, top);
	}
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
	vector<vector<int>> childs(N);
	vector<pair<int, bset>> members(M, {0, bset()});
	bset dfsStorage;

	for (int x = 0; x < N; x++)
		dfs(dfsStorage, F, x, childs);

	bset target;
	int top = 0, days = 0;

	do {
		{
			int node = S[0][top];
			members[0].second[node] = 1;
			for (int c: childs[node]) {
				if (target[c]) continue;
				add_childs(childs, c, target, members[0].second, top);
			}

			target[node] = 1;
		}

		top++;
		do {
			for (int r = 0; r < M; r++) {
				int& rtop = members[r].first;
				while (rtop < top) {
					int node = S[r][rtop++];
					members[r].second[node] = 1;

					for (int c: childs[node]) {
						if (target[c]) continue;
						add_childs(childs, c, target, members[r].second, top);
					}

					if (target[node]) continue;
					top++, target[node] = 1;
				}
			}
		} while (members[0].first != members[M - 1].first);

		days++;
	} while (1 + top < N);

	return days;
}

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