| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1171340 | gulmix | September (APIO24_september) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()
#define oset tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
const ll MOD = 1e9 + 7, N = 2e5 + 5;
vector<ll> graph[N];
ll dp[N];
void dfs(ll v, ll p){
for(auto u: graph[v]){
if(u != p){
dfs(u, v);
dp[v] = max(dp[v], dp[u]);
}
}
}
ll solve(ll n, ll m, vector<ll> g, vector<vector<ll>> rec){
for(int i = 1; i < n; i++){
graph[i].push_back(g[i]);
graph[g[i]].push_back(i);
}
for(ll i = 0; i < m; i++){
for(ll j = 0; j < n-1; j++){
dp[rec[i][j]] = max(dp[rec[i][j]], j);
}
}
dfs(0, -1);
ll last = -1, ans = 0;
for(ll i = 0; i < n - 1; i++){
if(last < i)ans++;
ll mx = 0;
for(ll j = 0; j < m; j++){
mx = max(mx, dp[rec[j][i]]);
}
last = max(last, mx);
}
for(int i = 0; i < n; i++){
graph[i].clear();
dp[i] = 0;
}
return ans;
}
//int main(){
// ios::sync_with_stdio(false);
// cin.tie(0);
// //ifstream cin("fstncd.in");
// //ofstream cout("fstncd.out");
//
//}