oj.uz

Submission #531529

# Submission time Handle Problem Language Result Execution time Memory
531529 2022-03-01T02:02:33 Z zlxFTH Torrent (COI16_torrent) C++11
100 / 100
 318 ms 24856 KB 
#include<bits/stdc++.h>
#define LL long long
#define Rep(i,x,y) for(int i = (x), stOxrj = (y); i <= stOxrj; ++i)
#define Irep(i,x,y) for(int i = (x), stOxrj = (y); i >= stOxrj; --i)
#define il inline
#define let const auto
#define ci const int&
#define VEC vector<int>
#define pb emplace_back
#define MP make_pair
#define PA pair<int, int>
#define fi first
#define se second
#define IT iterator
using namespace std;
il int read(){
	int res = 0, flag = 1; char c = getchar();
	while( c < '0' || c > '9' ){ if( c == '-' ) flag = -1; c = getchar(); }
	while( c >= '0' && c <= '9' ) res = res * 10 + c - '0', c = getchar();
	return res * flag;
}
const int N = 3e5 + 20;
VEC e[N];
int ba, bb, n, s, t;
bool same(ci u, ci v){
	return u + v == ba + bb && abs(u - v) == abs(ba - bb);
}
int fa[N], f[N];
int nb[N];
void dfs(int u, int fat){
	fa[u] = fat;
	for(int v : e[u]) if(v != fat && !same(u, v)) dfs(v, u);
	int res = 0, cnt = 0;
	for(int v : e[u]) if(v != fat && !same(u, v)) nb[++cnt] = f[v];
	sort(nb + 1, nb + cnt + 1, [&](ci A, ci B){ return A > B; });
	Rep(i, 1, cnt) res = max(res, i + nb[i]);
	f[u] = res;	
}
int link[N], ln;
PA Solve(int x){
	ba = link[x], bb = link[x + 1];
	dfs(s, 0), dfs(t, 0);
	return MP(f[s], f[t]);
}
signed main(){
//	freopen("rorrent.in", "r", stdin);
//	freopen("rorrent.out", "w", stdout);
	n = read(), s = read(), t = read();
	Rep(i, 2, n){
		int u = read(), v = read();
		e[u].pb(v), e[v].pb(u);
	}
	dfs(t, 0);
	int ss = s;
	link[++ln] = s;
	while(ss != t) link[++ln] = ss = fa[ss];

	PA cur;
	int l = 1, r = ln - 1;
	while(l < r){
		int mid = l + r >> 1;
		cur = Solve(mid);
		if(cur.fi < cur.se) l = mid + 1;
		else r = mid;
	}
	cur = Solve(l);
	int ans = max(cur.fi, cur.se);
	if(l != 1){
		cur = Solve(l - 1);
		ans = min(ans, max(cur.fi, cur.se));
	}	
	cout<<ans<<'\n';
	return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:61:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 21692 KB Output is correct
2 Correct 318 ms 24060 KB Output is correct
3 Correct 279 ms 24040 KB Output is correct
4 Correct 259 ms 24856 KB Output is correct
5 Correct 299 ms 22104 KB Output is correct
6 Correct 260 ms 22280 KB Output is correct
7 Correct 225 ms 24772 KB Output is correct