Submission #1187704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187704		PieArmy	Mousetrap (CEOI17_mousetrap)	C++20	45 / 100	714 ms	111688 KiB

mousetrap

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

int n,t,r,m;
int par[1000023],spec[1000023];
int dp[1000023],ek[1000023];
vector<int>komsu[1000023];
vector<int>res[1000023];
vector<int>specs;
int locs[1000023];

void dfs1(int pos){
	ek[pos]=ek[par[pos]]+max(0,int(komsu[pos].size())-2+(pos==r));
	if(pos==t)ek[pos]=0;
	for(int x:komsu[pos]){
		if(x==par[pos])continue;
		par[x]=pos;
		dfs1(x);
		spec[pos]|=spec[x];
	}
	if(spec[pos]){
		specs.pb(pos);
	}
}

void dfs2(int pos){
	for(int x:komsu[pos]){
		if(x==par[pos])continue;
		if(spec[x])continue;
		dp[pos]++;
		dfs2(x);
		res[pos].pb(dp[x]);
	}
	sort(res[pos].begin(),res[pos].end(),[&](const int &x,const int &y){return x>y;});
	if(dp[pos]<=1){
		return;
	}
	dp[pos]+=res[pos][1];
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>t>>r;
	spec[r]=1;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb(y);
		komsu[y].pb(x);
	}
	dfs1(t);
	specs.pop_back();
	int m=specs.size();
	for(int i:specs){
		dfs2(i);
	}
	priority_queue<pair<int,int>>pq;
	for(int i=0;i<m;i++){
		locs[i]=0;
		if(res[specs[i]].size()){
			pq.push({res[specs[i]][locs[i]]+ek[specs[i]],i});
		}
	}
	int ans=0;
	for(int i=0;i<m;i++){
		while(pq.size()&&pq.top().sc<i)pq.pop();
		if(pq.size()){
			pair<int,int>p=pq.top();
			pq.pop();
			locs[p.sc]++;
			if(locs[p.sc]<res[specs[p.sc]].size()){
				pq.push({res[specs[p.sc]][locs[p.sc]]+ek[specs[p.sc]],p.sc});
			}
		}
		int cur=ek[specs[i]]+(locs[i]>=res[specs[i]].size()?0:res[specs[i]][locs[i]]);
		ans=max(ans,cur);
	}
	cout<<ans<<endl;
}

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