Submission #704595

#	Time	Username	Problem	Language	Result	Execution time	Memory
704595		amirhoseinfar1385	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	919 ms	207644 KiB

mousetrap

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000000+5;
vector<int>adj[maxn],alldp[maxn];
int par[maxn],vis[maxn],n,t,m,dp[maxn],ted[maxn],mainres;
int val[maxn],high[maxn];

struct compare
{
    bool operator()(const pair<int,int> & a, const pair<int,int> & b)
    {
        if(a.first==b.first){
        	return high[a.second]>high[b.second];
        }
        return a.first>b.first;
    }
};

priority_queue<pair<int,int>,vector<pair<int,int>>,compare>pq;


void dfs(int u,int para=0){
	par[u]=para;
	high[u]=high[para]+1;
	for(int x:adj[u])
	{
		if(x!=para){
			dfs(x,u);
			vis[u]|=vis[x];
			if(vis[x]==0){
				ted[u]++;
				alldp[u].push_back(dp[x]);
			}	
		}
	}
	if((int)alldp[u].size()>0){
		if((int)alldp[u].size()==1){
			dp[u]=2;
		}
		else{
			sort(alldp[u].begin(),alldp[u].end());
			int maxa1=alldp[u].back(),maxa2=alldp[u][(int)alldp[u].size()-2];
			dp[u]=maxa2+ted[u]-1;
			dp[u]++;
		}
	}	
	else{
		dp[u]=1;
	}
}

void solve(int had){
	int allted=0,now=had;
	while(now!=t){
		//cout<<"1 "<<now<<endl;
		allted+=ted[now];
		now=par[now];
	}
	int fted=allted;
	now=had;
	int unnow=1;
	while(now!=t){
		int ffted=allted;
		for(int i=(int)alldp[now].size()-1;i>=0;i--){
			int x=alldp[now][i]+allted-1+(int)pq.size();
			if((int)pq.size()<unnow){
				pq.push(make_pair(x,now));
				val[now]++;
				allted--;
			}
			else{
				pair<int,int> y=pq.top();
				if(y.first<=x){
					pq.pop();
					pq.push(make_pair(x,now));
					val[y.second]--;
					val[now]++;
					allted--;
					if(y.second==now){
						allted++;
					}
				}
			}
		}
		allted=ffted-ted[now];
		now=par[now];
		unnow++;
	}
	allted=fted;
	int resa=(int)pq.size();
	now=had;
	int fn=0;
	while(now!=t){
		for(int i=0;i<(int)alldp[now].size()-(val[now]-fn);i++){
			int x=alldp[now][i]+allted-1;
		//	cout<<now<<" asd "<<x<<"\n";
			resa=max(resa,x+fn);
		}
		allted-=ted[now];
		fn=val[now];
		val[par[now]]+=val[now];
		now=par[now];
	}
	mainres=resa;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>t>>m;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vis[m]=1;
	dfs(t);
	solve(m);
	cout<<mainres<<"\n";
}

Compilation message (stderr)

mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:43:8: warning: unused variable 'maxa1' [-Wunused-variable]
   43 |    int maxa1=alldp[u].back(),maxa2=alldp[u][(int)alldp[u].size()-2];
      |        ^~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35