Submission #1202721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202721		randnt93	September (APIO24_september)	C++20	0 / 100	7 ms	13200 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 (rem[c]) continue;
		rem[c] = 1;
		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(N, {0, bset()});
	bset dfsStorage;

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

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

	do {
		target[S[0][top]] = 1;
		members[0].first++, members[0].second[S[0][top]] = 1;
		top++;

		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 (members[r].second[c]) continue;
					add_childs(childs, c, target, members[r].second, top);
				}

				if (target[node]) continue;
				top++, target[node] = 1;
			}
		}

		days++;
	} while (1 + top < 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