Submission #1292096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292096		Hamed_Ghaffari	September (APIO24_september)	C++20	100 / 100	102 ms	10984 KiB

september

#include "september.h"
#include <bits/stdc++.h>
using namespace std;

const int MXN = 1e5 + 5;

vector<int> g[MXN];
int cnt[MXN];
bool mark[MXN];

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
	for(int i=0; i<N; i++) g[i].clear(), cnt[i] = 0, mark[i] = 0;
	for(int i=1; i<N; i++) g[F[i]].push_back(i);
	int ans=0, dad=0, nt=0;
	auto add = [&](int v) {
		if(cnt[v]==0) nt++;
		cnt[v]++;
		if(cnt[v]==M) nt--;
		if(mark[v]) return;
		if(v && mark[F[v]]) dad--;
		mark[v] = 1;
		for(int u : g[v])
			if(!mark[u])
				dad++;
	};
	for(int l=0; l<N-1;) {
		ans++;
		for(int i=0; i<M; i++) add(S[i][l]);
		int r=l;
		while(nt || dad) {
			r++;
			for(int i=0; i<M; i++)
				add(S[i][r]);
		}
		l = r+1;
	}
	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