# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1195624 | agrim_09 | September (APIO24_september) | C++20 | 0 ms | 0 KiB |
#include "september.h"
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int m, vector<int>&par, vector<vector<int>>&obs) {
for(int i = 0;i<m;i++){
obs[i].push_back(0);
}
vector<bool>in_stack(n,false);
vector<int>to_take(n);
for(int i = 1;i<n;i++){
to_take[par[i]]++;
}
vector<bool>is_fine(n,false);
vector<int>vec = obs[0];
int stack_size = 0;
for(int i = 0;i<n-1;i++){
int u = vec[i];
in_stack[u] = true;
stack_size++;
if(to_take[u]==0){
stack_size--; in_stack[u] = false;
if(par[u]!=-1){
to_take[par[u]]--;
if(to_take[par[u]]==0 and in_stack[par[u]]){
stack_size--;
in_stack[par[u]] = false;
}
}
}
else{
if(par[u]!=-1){
to_take[par[u]]--;
if(to_take[par[u]]==0 and in_stack[par[u]]){
stack_size--;
in_stack[par[u]] = false;
}
}
}
if(stack_size==0){
is_fine[i] = true;
}
}
int x = accumulate(is_fine.begin(),is_fine.end(),0);
return x;
}