Submission #1155739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155739		blackslex	September (APIO24_september)	C++20	100 / 100	147 ms	10760 KiB

september

#include "september.h"
#include <vector>
#include<bits/stdc++.h>

using namespace std;

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	int n = N, m = M;
	vector<vector<int>> v(n, vector<int>());
	vector<vector<bool>> f(m, vector<bool>(n));
	vector<bool> f2(n);
	multiset<int> ms;
	for (int i = 1; i < n; i++) {
		v[F[i]].emplace_back(i);
	}
	auto dfs = [&] (auto &&dfs, int cur, int par, int idx) -> void {
		if (f[idx][cur]) return; f[idx][cur] = 1;
		if (!f2[cur]) {
			f2[cur] = 1;
			for (int i = 0; i < m; i++) ms.emplace(cur);
		}
		for (auto &e: v[cur]) {
			if (par == e) continue;
			dfs(dfs, e, cur, idx);
		}
	};
	int ans = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m; j++) dfs(dfs, S[j][i], -1, j);
		for (int j = 0; j < m; j++) ms.erase(ms.find(S[j][i]));
		if (ms.empty()) ans++;
	}
	return ans;
	return 0;
}

• 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