Submission #786110

#	Time	Username	Problem	Language	Result	Execution time	Memory
786110		vjudge1	Tax Evasion (LMIO19_mokesciai)	C++17	100 / 100	164 ms	50088 KiB

mokesciai

#include<bits/stdc++.h>
using namespace std;
int n, m, cnt, x;
int par[18][200005], dep[200005], lft[200005], rgt[200005];
bool b[200005];
vector<int> adjl[200005], que[200005], order;
 
void tour(int x){
	order.push_back(x);
	lft[x]=cnt++;
	for(int i:adjl[x]){
		tour(i);
	}
	rgt[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[lft[up]].push_back(rgt[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;
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 39 / 39
• Subtask 4: 29 / 29