oj.uz

Submission #99181

# Submission time Handle Problem Language Result Execution time Memory
99181 2019-03-01T14:18:47 Z dsg213 Torrent (COI16_torrent) C++14
100 / 100
 1368 ms 44956 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
const int mod=1000000007,mxn=1000010;
int ost[mxn];
vector<int> pol[mxn];
void dfs1(int v,int p){
	ost[v]=p;
	for(int i=0;i<pol[v].size();i++){
		int u=pol[v][i];
		if(u==p){
			continue;
		}
		dfs1(u,v);
	}
}
int dfs2(int v,int p,int om){
	vector<int> vec(1,0);
	for(int i=0;i<pol[v].size();i++){
		int u=pol[v][i];
		if(u==p || u==om){
			continue;
		}
		vec.pb(dfs2(u,v,om)+1);
	}
	sort(vec.begin(),vec.end());
	reverse(vec.begin(),vec.end());
	int mx=0;
	for(int i=0;i<vec.size();i++){
		mx=max(mx,i+vec[i]);
	}
	return mx;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,a,b,c,d;
	cin >>n >>a >>b;
	for(int i=0;i<n-1;i++){
		cin >>c >>d;
		pol[c].pb(d);
		pol[d].pb(c);
	}
	dfs1(a,0);
	vector<int> dro;
	int x=b;
	while(x!=0){
		dro.pb(x);
		x=ost[x];
	}
	/*for(int i=0;i<dro.size();i++){
		cout <<dro[i] <<" ";
	}*/
	int wyn=1e9;
	int mn=0,mx=dro.size()-1;
	while(mn<mx){
		int sr=(mn+mx)/2;
		int w1=dfs2(a,0,dro[sr]);
		int w2=dfs2(b,0,dro[sr+1]);
		wyn=min(wyn,max(w1,w2));
		if(w1>w2){
			mn=sr+1;
		}
		else{
			mx=sr;
		}
	}
	cout <<wyn;
}

Compilation message

torrent.cpp: In function 'void dfs1(int, int)':
torrent.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pol[v].size();i++){
              ~^~~~~~~~~~~~~~
torrent.cpp: In function 'int dfs2(int, int, int)':
torrent.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pol[v].size();i++){
              ~^~~~~~~~~~~~~~
torrent.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++){
              ~^~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23936 KB Output is correct
2 Correct 28 ms 23936 KB Output is correct
3 Correct 27 ms 23932 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 1368 ms 37376 KB Output is correct
2 Correct 1358 ms 43056 KB Output is correct
3 Correct 1252 ms 44564 KB Output is correct
4 Correct 1134 ms 43916 KB Output is correct
5 Correct 1119 ms 40888 KB Output is correct
6 Correct 870 ms 41308 KB Output is correct
7 Correct 792 ms 44956 KB Output is correct