Submission #54487

# Submission time Handle Problem Language Result Execution time Memory
54487 2018-07-03T15:44:24 Z Pajaraja Torrent (COI16_torrent) C++17
31 / 100
2000 ms 19288 KB
#include <bits/stdc++.h>
using namespace std;
vector<int> g[300007],v;
int n,a,b;
bool ld,zb[300007];
void fr(int s,int f)
{
	if(s==b) ld=true;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !ld) fr(g[s][i],s);
	if(ld) {v.push_back(s); return;}
}
int calc(int s,int f)
{
	priority_queue<int> pq;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !zb[g[s][i]]) pq.push(calc(g[s][i],s));
	int maxv=0,cnt=1;
	while(!pq.empty())
	{
		maxv=max(maxv,pq.top()+cnt);
		pq.pop();
		cnt++;
	}
	return maxv;
}
int val(int x)
{
	zb[v[x+1]]=true;
	int v1=calc(a,0);
	zb[v[x+1]]=false;
	zb[v[x]]=true;
	int v2=calc(b,0);
	zb[v[x]]=false;
	return max(v1,v2);
}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	for(int i=0;i<n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	fr(a,0);
	int l=0,r=v.size()-2;
	reverse(v.begin(),v.end());
	while(r-l>50)
	{
		int s1=(2*l+r)/3;
		int s2=(l+2*r)/3;
		int x=val(s1),y=val(s2);
		if(x>y) l=s1;
		else r=s2;
	}
	int minv=n+1;
	for(int i=l;i<=r;i++) minv=min(minv,val(i));
	printf("%d",minv);
}

Compilation message

torrent.cpp: In function 'void fr(int, int)':
torrent.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !ld) fr(g[s][i],s);
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int calc(int, int)':
torrent.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !zb[g[s][i]]) pq.push(calc(g[s][i],s));
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~
torrent.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 10 ms 7420 KB Output is correct
2 Correct 11 ms 7528 KB Output is correct
3 Correct 11 ms 7528 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 19288 KB Time limit exceeded
2 Halted 0 ms 0 KB -