oj.uz

Submission #76521

# Submission time Handle Problem Language Result Execution time Memory
76521 2018-09-14T12:00:22 Z harunsami Torrent (COI16_torrent) C++
100 / 100
 552 ms 26112 KB 
#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define endll puts("")
#define mod 1000000007
#define ll long long
#define mp3(a,b,c) mp(a,mp(b,c))
#define sol (root+root)
#define sag (sol+1)
#define ort ((son+bas)/2)
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
const int N=3e5+3;
int a,b,n,m,ans=1e9,x,y,z,h[N],hh[N],k,l,i,j,ii,jj,t,s,A,B;
vector<int> V[N],v;
int dfs1(int x,int ata)
{
	if(x==b)return 1;
	int y=0,t;
	for(int i=0;i<V[x].size();i++)
		if(V[x][i]!=ata)
		{
			t=dfs1(V[x][i],x);
			if(t){y=1;v.pb(V[x][i]);}	
		}
	return y;
}
int dfs2(int x,int ata)
{
	vector<int>vv;
	int a,t=0;
	for(int i=0;i<V[x].size();i++)
		if(V[x][i]!=ata and (A+B!=x+V[x][i] or (A!=x and A!=V[x][i])))
		{
			a=dfs2(V[x][i],x);
			vv.pb(a);
		}
	sort(vv.rbegin(),vv.rend());
	for(int i=0;i<vv.size();i++)
		t=max(t,i+1+vv[i]);
	return t;
}
int main()
{
	cin>>n>>a>>b;
	for(i=1;i<=n-1;i++)
	{
		scanf("%d %d",&x,&y);
		V[x].pb(y);
		V[y].pb(x);
	}
	v.pb(b);
	dfs1(a,0);
	v.pb(a);
	int bas=1,son=v.size();
	while(bas<son)
	{
		A=v[ort];B=v[ort-1];
	
		t=dfs2(b,0);
		s=dfs2(a,0);
		
		ans=min(ans,max(t,s));
		if(t>s)son=ort;
		else bas=ort+1;
	}
	cout<<ans<<endl;
}

Compilation message

torrent.cpp: In function 'int dfs1(int, int)':
torrent.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<V[x].size();i++)
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int dfs2(int, int)':
torrent.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<V[x].size();i++)
              ~^~~~~~~~~~~~
torrent.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vv.size();i++)
              ~^~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:69: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 9 ms 7416 KB Output is correct
2 Correct 9 ms 7548 KB Output is correct
3 Correct 11 ms 7548 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 21216 KB Output is correct
2 Correct 523 ms 24284 KB Output is correct
3 Correct 486 ms 25732 KB Output is correct
4 Correct 544 ms 25732 KB Output is correct
5 Correct 516 ms 25732 KB Output is correct
6 Correct 509 ms 25732 KB Output is correct
7 Correct 457 ms 26112 KB Output is correct