oj.uz

Submission #116154

# Submission time Handle Problem Language Result Execution time Memory
116154 2019-06-11T03:21:55 Z user202729 Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 5000 ms 73244 KB 
// 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?
	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<<' '<<x<<" dfs3-> "<<ans<<'\n');
		n_impos+=!dfs3(child,x);
	}
	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;
	}
	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
*/

Compilation message

mousetrap.cpp: In function 'bool dfs3(int, int)':
mousetrap.cpp:43:8: warning: unused variable 'ans' [-Wunused-variable]
   bool ans=dfs3(child,x);
        ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5095 ms 73244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 143 ms 452 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 344 ms 504 KB Output is correct
17 Incorrect 3 ms 384 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Execution timed out 5095 ms 73244 KB Time limit exceeded
12 Halted 0 ms 0 KB -