제출 #1200793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200793		crispxx	September (APIO24_september)	C++20	100 / 100	499 ms	19392 KiB

september

#include "september.h"

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

#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

// #include "stub.cpp"

int solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s) {
	vector<vector<int>> adj(n);
	
	for(int i = 1; i < n; i++) {
		adj[f[i]].pb(i);
	}
	
	vector<int> tin(n), tout(n);
	
	int timer = 0;
	
	auto dfs = [&](auto &&self, int v) -> void {
		tin[v] = ++timer;
		for(auto to : adj[v]) {
			self(self, to);
		}
		tout[v] = timer;
	};
	
	dfs(dfs, 0);
	
	set<pair<int, int>> st;
	
	for(int i = 1; i < n; i++) {
		st.emplace(tin[i], i);
	}
	
	vector<int> mx(n);
	
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n - 1; j++) {
			int v = s[i][j];
			mx[v] = max(mx[v], j);
		}
	}
	
	int j = 0, k = 0;
	
	auto update = [&](int u) {
		vector<int> del;
		for(auto it = st.lower_bound({tin[u], 0}); it != st.end(); it++) {
			int v = it -> second;
			if(!(tin[v] >= tin[u] && tout[v] <= tout[u])) break;
			k = max(k, mx[v]);
			del.pb(v);
		}
		for(auto &x : del) {
			st.erase({tin[x], x});
		}
	};
	
	auto add = [&]() {
		for(int i = 0; i < m; i++) {
			update(s[i][j]);
		}
		j++;
	};
	
	int ans = 0;
	
	while(j < n - 1) {
		do {
			add();
		} while(j <= k);
		ans++;
	}
	
	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