| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 786109 | vjudge1 | Tax Evasion (LMIO19_mokesciai) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int n, m, cnt, x;
int par[18][200005], dep[200005], left[200005], right[200005];
bool b[200005];
vector<int> adjl[200005], que[200005], order;
void tour(int x){
order.push_back(x);
left[x]=cnt++;
for(int i:adjl[x]){
tour(i);
}
right[x]=cnt;
}
int anc(int x, int dp){
for(int i=17; i>=0; i--){
if(dp&(1<<i)) x=par[i][x];
}
return x;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i=2; i<=n; i++){
cin >> x;
par[0][i]=x;
dep[i]=dep[x]+1;
adjl[x].push_back(i);
}
for(int i=1; i<18; i++){
for(int j=1; j<=n; j++){
par[i][j]=par[i-1][par[i-1][j]];
}
}
for(int i=0; i<m; i++){
cin >> x;
b[x]=1;
}
tour(1);
for(int i=1; i<=n; i++){
if(b[i]){
int up=anc(i, (dep[i]-1)/2);
que[left[up]].push_back(right[up]);
}
}
int res=0, mid, l=0, r=n;
while(l<=r){
mid=(l+r)/2;
priority_queue<int, vector<int>, greater<int>> pq;
bool can=1;
for(int i=0; i<n && can; i++){
for(int j:que[i]) pq.push(j);
if(dep[order[i]]>=mid && !pq.empty()){
int x=pq.top();
pq.pop();
if(x<=i) can=0;
}
}
if(!pq.empty()) can=0;
if(can){
res=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout << res+1 << endl;
}