Submission #995615

#	Time	Username	Problem	Language	Result	Execution time	Memory
995615		avighna	September (APIO24_september)	C++17	100 / 100	274 ms	16840 KiB

september

#include "september.h"

#include <bits/stdc++.h>

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	std::vector<std::vector<int>> sizes(M, std::vector<int>(N));
	std::vector<std::vector<bool>> is_leaf(M, std::vector<bool>(N));
	std::vector<std::vector<int>> adj(N);
	for (int i = 1; i < N; ++ i) {
		for (int j = 0; j < M; ++ j) {
			sizes[j][i]++;
			sizes[j][F[i]]++;
		}
		adj[i].push_back(F[i]);
		adj[F[i]].push_back(i);
	}

	std::vector<std::vector<int>> pos(M, std::vector<int>(N));
	for (int j = 0; j < M; ++ j) {
		for (int i = 0; i < N - 1; ++ i) {
			pos[j][S[j][i]] = i;
		}
	}

	std::vector<std::set<std::pair<bool, std::pair<int, int>>>> sts(M);

	for (int i = 1; i < N; ++ i) {
		for (int j = 0; j < M; ++ j) {
			if (sizes[j][i] == 1) {
				is_leaf[j][i] = true;
			}
		}
	}

	int ans = 0;
	std::vector<std::vector<bool>> removed(M, std::vector<bool>(N));
	std::vector<std::vector<bool>> queued(M, std::vector<bool>(N));
	std::vector<int> listPtrs(M);
	for (int i = 0; i < N - 1; ++ i) {
		int end_at = i;
		std::queue<int> q;
		for (int j = 0; j < M; ++ j) {
			q.push(S[j][listPtrs[j]]);
		}
		while (!q.empty()) {
			int node = q.front();
			q.pop();
			for (int j = 0; j < M; ++ j) {
				sts[j].insert({!is_leaf[j][node], {pos[j][node], node}});
				queued[j][node] = true;
				end_at = std::max(end_at, pos[j][node]);
			}
			for (int j = 0; j < M; ++ j) {
				for (; listPtrs[j] <= end_at; ++ listPtrs[j]) {
					q.push(S[j][listPtrs[j]]);
				}
			}
		}
		i = end_at;
		int cur = 0;
		for (int j = 0; j < M; ++ j) {
			auto &st = sts[j];
			while (!st.empty()) {
				auto p = *st.begin();
				if (p.first) {
					break;
				}
				int node = p.second.second;
				st.erase(st.begin());

				for (auto &i : adj[node]) {
					if (!removed[j][i]) {
						sizes[j][i]--;
					}
				}
				sizes[j][node] = 0;
				removed[j][node] = true;

				for (auto &i : adj[node]) {
					if (i != 0 && sizes[j][i] == 1) {
						is_leaf[j][i] = true;
						if (queued[j][i]) {
							st.erase({!false, {pos[j][i], i}});
							st.insert({!true, {pos[j][i], i}});
						}
					}
				}
			}
			if (st.empty()) {
				cur++;
			}
		}
		ans += cur == M;
	}

	return ans;
}

• 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