Submission #1277271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277271		tasso7	September (APIO24_september)	C++20	100 / 100	135 ms	12200 KiB

september

#include "september.h"
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<bool> caduti;

vector<vector<int>> adj;
int M;
vector<int> edv;

void DFS(int n){
	//cout<<"D:"<<n << endl;
	if(caduti[n]){return;}
	//cout << "=>" << endl;
	caduti[n] = true;
	for(int j = 0; j < M; j++){edv[j]++;}
	for(int k : adj[n]){DFS(k);}
	//cout << "-" << endl;
}

int solve(int N, int m, std::vector<int> F, std::vector<std::vector<int>> S) {
	M = m;
	//caso M = 1
	adj = vector<vector<int>>(N, vector<int>{});
	caduti=vector<bool>(N,false);
	for(int i = 1; i < N; i++){
		adj[F[i]].push_back(i);
	}

	edv = vector<int>(M, 0);
	vector<int> i = vector<int>(M, 0);

	int g = 0;
	
	while(*min_element(i.begin(), i.end()) < N-1){
		for(int j = 0; j < M; j++){
			if(i[j] == N-1){continue;}
			DFS(S[j][i[j]]);
			edv[j]--;
			i[j]++;
			break;
		}
		g++;
		while(*max_element(edv.begin(), edv.end()) > 0){
			for(int j = 0; j < M; j++){
				while(edv[j] != 0 && i[j] < N-1){
					DFS(S[j][i[j]]);
					edv[j]--;
					i[j]++;
				}
			}
		}
	}
	
	return g;
}

• 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