# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1200709 | aaatroush | September (APIO24_september) | C++20 | 0 ms | 0 KiB |
#include "september.h"
#include <bits/stdc++.h>
#define ll long long
#define ull long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
int solve(int n, int m, vector<int> F, vector<vector<int>> vol) {
vector<vector<ll>> adj(n);
for(ll i = 1; i<F.size(); i++){
adj[F[i]].pb(i);
}
/*for(ll i = 0; i<n; i++){
cout<<i<<": ";
for(auto &child:adj[i]){
cout<<child<<" ";
}
cout<<endl;
}*/
ll mi = LLONG_MAX;
for(ll i = 0; i<vol.size(); i++){
vector<int> vec = vol[i];
ll ctr = 0;
set<int> removal;
vector<bool> visited(n, 0);
for(int i = 0; i <vec.size(); i++){
if(removal.empty()){
ctr++;
}
removal.erase(vec[i]);
queue<ll> bfs;
bfs.push(vec[i]);
visited[vec[i]] = 1;
while(!bfs.empty()){
ll parent = bfs.front();
visited[parent] = 1;
bfs.pop();
for(auto &child:adj[parent]){
if(!visited[child]){
bfs.push(child);
removal.insert(child);
}
}
}
}
mi = min(mi, ctr);
}
return mi;
}
int main(){
cout<<solve(3, 1, {-1,0,0}, {{1, 2}});
}