oj.uz

Submission #76470

# Submission time Handle Problem Language Result Execution time Memory
76470 2018-09-13T14:42:44 Z ekrem Torrent (COI16_torrent) C++
100 / 100
 691 ms 43960 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)>>1)
#define N 1000005
using namespace std;

typedef vector < int > vi;

int n, m, a, b, x, y, bas, son, c[N];
vector < int > g[N];

bool dfs(int node, int par){
	if(node == b){
		c[++m] = node;
		return 1;
	}
	for(int i = 0; i < g[node].size(); i++)
		if(g[node][i] != par)
			if(dfs(g[node][i], node)){
				c[++m] = node;
				return 1;
			}
	return 0;
}

inline bool git(int a, int b){return !((a == x and b == y) or (b == x and a == y));}

int bul(int node, int par){
	vi d;
	for(int i = 0; i < g[node].size(); i++)
		if(g[node][i] != par and git(node, g[node][i]))
			d.pb(bul(g[node][i], node));
	sort(d.begin(), d.end());
	reverse(d.begin(), d.end());
	int mx = 0;
	for(int i = 0; i < d.size(); i++)
		mx = max(mx, i + 1 + d[i]);
	return mx;
}

int main(){
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d %d",&n ,&a ,&b);
	for(int i = 1; i < n; i++){
		int u, v;
		scanf("%d %d",&u ,&v);
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(a, 0);
	reverse(c + 1, c + m + 1);
	// for(int i = 1; i <= m; i++)cout << c[i] << " ";cout << endl;
	bas = 1;
	son = m;
	while(son - bas > 2){
		x = c[orta];
		y = c[orta + 1];
		int ilk = bul(a, 0);
		int iki = bul(b, 0);
		if(ilk > iki)
			son = orta + 1;
		else
			bas = orta;
	}
	// cout << c[bas] << " " << c[son] << endl;
	x = c[bas];
	y = c[bas + 1];
	// cout << bul(a, 0) << " " << bul(b, 0) << endl;
	int mn = max(bul(a, 0) , bul(b, 0));
	if(son == bas + 1)
		printf("%d\n",mn);
	else{
		x = c[bas + 1];
		y = c[son];
		printf("%d\n", min(mn, max(bul(a, 0) , bul(b, 0)) ));
	}

	return 0;
}

Compilation message

torrent.cpp: In function 'bool dfs(int, int)':
torrent.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
torrent.cpp: In function 'int bul(int, int)':
torrent.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
torrent.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < d.size(); i++)
                 ~~^~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:47: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:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u ,&v);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23932 KB Output is correct
3 Correct 26 ms 23976 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 39660 KB Output is correct
2 Correct 662 ms 42440 KB Output is correct
3 Correct 576 ms 43744 KB Output is correct
4 Correct 630 ms 43744 KB Output is correct
5 Correct 691 ms 43744 KB Output is correct
6 Correct 601 ms 43744 KB Output is correct
7 Correct 567 ms 43960 KB Output is correct