Submission #1187733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187733		PieArmy	Mousetrap (CEOI17_mousetrap)	C++20	100 / 100	553 ms	203960 KiB

mousetrap

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define mid ((left+right)>>1)
#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];
}

bool f(int x){
	int used=0;
	for(int i=0;i<m;i++){
		int pos=specs[i];
		int itr=0;
		while(itr<res[pos].size()){
			if(res[pos][itr]+ek[pos]+used>x)itr++;
			else break;
		}
		if(itr==res[pos].size()){
			if(ek[pos]+used>x)return false;
		}
		if(itr+used>i+1)return false;
		used+=itr;
	}
	return true;
}

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();
	m=specs.size();
	for(int i:specs){
		dfs2(i);
	}
	int l=0,r=n;
	while(l<r){
		int m=(l+r)/2;
		if(f(m))r=m;
		else l=m+1;
	}
	cout<<l<<endl;
}

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