Submission #54485

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
54485	2018-07-03T15:41:53 Z	Pajaraja	Torrent (COI16_torrent)	C++17	100 / 100	1930 ms	47540 KB

torrent

#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>3)
	{
		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);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	7416 KB	Output is correct
2	Correct	11 ms	7464 KB	Output is correct
3	Correct	10 ms	7476 KB	Output is correct

Subtask #2

69.0 / 69.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1930 ms	19432 KB	Output is correct
2	Correct	1636 ms	24632 KB	Output is correct
3	Correct	1836 ms	30896 KB	Output is correct
4	Correct	1784 ms	34016 KB	Output is correct
5	Correct	1866 ms	35456 KB	Output is correct
6	Correct	1738 ms	40376 KB	Output is correct
7	Correct	1379 ms	47540 KB	Output is correct