oj.uz

Submission #99180

# Submission time Handle Problem Language Result Execution time Memory
99180 2019-03-01T14:12:40 Z dsg213 Torrent (COI16_torrent) C++14
31 / 100
 2000 ms 41860 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;
	for(int i=0;i<dro.size()-1;i++){
		wyn=min(wyn,max(dfs2(a,0,dro[i]),dfs2(b,0,dro[i+1])));
		//cout <<a <<" "<<dro[i] <<"	" <<b <<" "<<dro[i+1] <<"\n";
	}
	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++){
              ~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dro.size()-1;i++){
              ~^~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23936 KB Output is correct
2 Correct 42 ms 23928 KB Output is correct
3 Correct 37 ms 24056 KB Output is correct

Subtask #2
0 / 69.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2021 ms 41860 KB Time limit exceeded
2 Halted 0 ms 0 KB -