Submission #116156

#	Time	Username	Problem	Language	Result	Execution time	Memory
116156		user202729	Mousetrap (CEOI17_mousetrap)	C++17	45 / 100	2840 ms	72668 KiB

mousetrap

// https://oj.uz/problem/view/CEOI17_mousetrap
#ifndef _GLIBCXX_DEBUG
#define NDEBUG
#endif

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#include<cassert>

int nn,trap,mouse;
std::vector<std::vector<int>> ad;

std::vector<int> par; // with root = trap
std::vector<int> nrock; // num of rock to put if mouse is trapped at [?]
// of course the mouse can only be trapped at nodes with <= 1 child (rooted somewhere)
void dfs1(int x){
	int const px=par[x];
	nrock[x]=nrock[px]+ad[x].size()-2;
	for(int child:ad[x])if(child!=px){
		par[child]=x;
		dfs1(child);
	}
}

std::vector<int> d1; // dist(?, line(trap, mouse))

std::vector<int> cost; // total cost if mouse is trapped at [?] = nrock + d1

int thr;
bool dfs3(int x,int par){ // is it possible to force mouse to be trapped at a node with cost <= thr ...
	// when start at x?
	// if(x==trap)return true;
	int nchild=ad[x].size()-(par>=0);
	if(nchild==0)return cost[x]<=thr;
	if(nchild==1){ // not sure about this, what if deg(mouse) == 1?
		if(cost[x]<=thr)return true;
		return false; // ???
	}
	int n_impos=0;
	for(int child:ad[x])if(child!=par){
		bool ans=dfs3(child,x);
		assert(std::cerr<<child+1<<' '<<x+1<<" dfs3-> "<<ans<<'\n');
		n_impos+=!ans;
	}
	return n_impos<=1;
}

int main(){
	std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
	std::cin>>nn>>trap>>mouse;
	if(trap==mouse){
		std::cout<<"0\n";
		return 0;
	}
	--trap;--mouse;
	ad.resize(nn);
	for(int u,v,_=nn-1;_--;){
		std::cin>>u>>v;--u;--v;
		ad[u].push_back(v);
		ad[v].push_back(u);
	}
	nrock.resize(nn);nrock[trap]=1;
	par.resize(nn);par[trap]=-1;
	for(int x:ad[trap]){
		par[x]=trap;
		dfs1(x);
	}

	d1.resize(nn,-1);
	std::queue<int> q;
	for(int x=mouse;x>=0;x=par[x]){
		q.push(x);
		d1[x]=0;
		if(par[x]==trap){
			ad[trap].assign(1,x); // remove unnecessary edges
		}
	}
	while(!q.empty()){
		int const x=q.front();q.pop();
		int const newd=d1[x]+1;assert(newd>0);
		for(int y:ad[x])if(d1[y]<0){
			d1[y]=newd;
			q.push(y);
		}
	}

	cost.resize(nn);
	std::transform(begin(nrock),end(nrock),begin(d1),begin(cost),std::plus<int>{});

	thr=nn;
	for(int r=1<<29;r;r>>=1){
		if(thr-r<0)continue;
		thr-=r;
		if(!dfs3(mouse,-1))
			thr+=r;
	}
	std::cout<<thr<<'\n';
	return 0;
}

/*
10 1 4  
1 2     
2 3     
2 4     
3 9     
3 5     
4 7     
4 6     
6 8     
7 10    

8 1 2 1 2 1 3 1 4 3 5 3 7 4 6 4 8

10 4 1  1 2 1 3 2 4 4 5 4 6 5 7 5 8 6 9 6 10
*/

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