Submission #1124242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124242		nikd	September (APIO24_september)	C++20	100 / 100	294 ms	16244 KiB

september

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

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
	vector<vector<int>> adj(N);
	for(int i = 1; i<N; i++){
		adj[i].push_back(F[i]);
		adj[F[i]].push_back(i);
	}
	vector<int>l(N, INT_MAX);
	vector<int>r(N, -1);
	for(int i = 0; i<M; i++){
		for(int j = 0; j<N-1; j++){
			l[S[i][j]] = min(l[S[i][j]], j);
			r[S[i][j]] = max(r[S[i][j]], j);
		}
	}

	auto dfs = [&](int v, int p, auto&& dfs) -> void{
		for(int u: adj[v]){
			if(u==p) continue;
			dfs(u, v, dfs);
			if(v != 0 && l[v] <= r[u]){
				l[v] = min(l[v], l[u]);
				r[v] = max(r[v], r[u]);
			}
		}
		return;
	};
	dfs(0, -1, dfs);
	vector<array<int, 2>> itv(N-1);
	for(int i = 1; i<N; i++) itv[i-1] = {l[i], r[i]};
	sort(itv.begin(), itv.end());
	int sol = 1;
	int curr_l = itv[0][0];
	int curr_r = itv[0][1];
	for(int i = 1; i<N-1; i++){
		if(curr_l <= itv[i][0] && itv[i][0] <= curr_r){
			curr_r = max(curr_r, itv[i][1]);
		}
		else{
			sol++;
			curr_l = itv[i][0]; curr_r = itv[i][1];
		}
	}
	return sol;
}

• 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