Submission #256652

#	Time	Username	Problem	Language	Result	Execution time	Memory
256652		nandonathaniel	Tax Evasion (LMIO19_mokesciai)	C++14	100 / 100	362 ms	46944 KiB

mokesciai

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005,LOG=18;

vector<int> adj[MAXN],que[MAXN];
int pa[LOG][MAXN],depth[MAXN],ST[MAXN],EN[MAXN],preorder[MAXN],idx;
bool coin[MAXN];

int anc(int u,int naik){
	for(int i=LOG-1;i>=0;i--){
		if(naik&(1<<i))u=pa[i][u];
	}
	return u;
}

void dfs(int now){
	idx++;
	ST[now]=idx;
	preorder[idx]=now;
	for(auto nxt : adj[now])dfs(nxt);	
	EN[now]=idx;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,m,p,a;
	cin >> n >> m;
	for(int i=2;i<=n;i++){
		cin >> p;
		adj[p].push_back(i);
		depth[i]=depth[p]+1;
		pa[0][i]=p;
		for(int j=1;j<LOG;j++)pa[j][i]=pa[j-1][pa[j-1][i]];
	}
	dfs(1);
	for(int i=1;i<=m;i++){
		cin >> a;
		coin[a]=true;
	}
	if(coin[1]){
		cout << 1 << '\n';
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(coin[i]){
			int atas=anc(i,(depth[i]-1)/2);
			que[ST[atas]].push_back(EN[atas]+1);
		}
	}
	int ki=0,ka=n,res;
	while(ki<=ka){
		int mid=(ki+ka)/2;
		priority_queue<int,vector<int>,greater<int> > PQ;
		bool yes=true;
		for(int i=1;i<=n;i++){
			for(auto isi : que[i])PQ.push(isi);
			if(!PQ.empty() && depth[preorder[i]]>=mid){
				if(PQ.top()<=i)yes=false;
				PQ.pop();
			}
		}
		if(yes && PQ.empty()){
			res=mid;
			ki=mid+1;
		}
		else ka=mid-1;
	}
	cout << res+1 << '\n';
	return 0;
}

Compilation message (stderr)

mokesciai.cpp: In function 'int main()':
mokesciai.cpp:68:19: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << res+1 << '\n';
                   ^~~~

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