Submission #288743

#	Time	Username	Problem	Language	Result	Execution time	Memory
288743		TadijaSebez	Mousetrap (CEOI17_mousetrap)	C++11	100 / 100	1080 ms	202616 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
const int N=1000050;
vector<int> E[N];
int dp[N],dep[N],n,t,m;
bool on[N];
void DP(int u,int p){
	vector<int> d;
	for(int v:E[u])if(v!=p){
		if(p)dp[v]=dp[u]+E[u].size()-2;
		DP(v,u);
		if(on[v])on[u]=1;
		d.pb(dp[v]);
	}
	sort(d.rbegin(),d.rend());
	if(d.size()>1)dp[u]=d[1];
	dp[u]+=E[u].size()>1;
}
vector<pii> tmp;
void DFS(int u,int p){
	if(u==t)return;
	for(int v:E[u])if(v!=p){
		dep[v]=dep[u]+1;
		if(on[u]&&!on[v])tmp.pb({dep[v],dp[v]+(u==m)});
		else DFS(v,u);
	}
}
bool Check(int mid){
	int need=0;
	for(auto p:tmp){
		if(need>p.first)return 0;
		if(p.second+need>mid)need++;
	}
	return need<=mid;
}
int main(){
	scanf("%i %i %i",&n,&t,&m);
	for(int i=1,u,v;i<n;i++)scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
	on[m]=1;dep[m]=-1;
	DP(t,0);
	DFS(m,0);
	sort(tmp.begin(),tmp.end());
	int top=n,bot=0,mid,ans;
	while(top>=bot){
		mid=top+bot>>1;
		if(Check(mid))ans=mid,top=mid-1;
		else bot=mid+1;
	}
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:47:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   mid=top+bot>>1;
      |       ~~~^~~~
mousetrap.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%i %i %i",&n,&t,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:40:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  for(int i=1,u,v;i<n;i++)scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
      |                          ~~~~~^~~~~~~~~~~~~~~

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