Submission #99181

#	Time	Username	Problem	Language	Result	Execution time	Memory
99181		dsg213	Torrent (COI16_torrent)	C++14	100 / 100	1368 ms	44956 KiB

torrent

#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 (stderr)

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 / 31
• Subtask 2: 69 / 69