This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (int i = s; i <= e; ++i)
#define rrep(i,s,e) for (int i = s; i >= e; --i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define len(a) (int)a.size()
typedef vector<int> vi;
const int mx = 1e6;
vi adj[mx+1], road;
int n, t, m;
bool dfs (int u, int p) {
if (u==t) return 1;
for (int v : adj[u]) {
if (v==p) continue;
if (dfs (v, u)) {
road.pb(u);
return 1;
}
}
return 0;
}
int dfs2 (int u, int p) {
if (len(adj[u])<=2) return len(adj[u])-1;
vi nxt;
for (int v : adj[u]) {
if (v==p) continue;
nxt.pb(dfs2 (v, u));
}
sort(all(nxt),greater<int>());
return nxt[1]+len(adj[u])-1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> t >> m;
rep (i,1,n-1) {
int u, v; cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs (m,-1);
int l = len(road), s = 0, lo = 0, hi = mx;
vi dp[l];
reverse(all(road));
road.pb(t);
rrep (i,l-1,0) {
s += max(len(adj[road[i]])-2+(i>0),0);
for (int v : adj[road[i]]) {
if ((i>0 && v==road[i-1]) || v==road[i+1]) continue;
dp[i].pb(dfs2(v,road[i])+s+1);
}
sort(all(dp[i]), greater<int>());
}
while (lo<hi) {
int mid = (lo+hi)/2, x = 0, suc = 1, cnt = 0;
rep (i,0,l-1) {
x++;
int nc = cnt;
for (int j : dp[i]) {
if (j+cnt>mid) {
x--;
nc++;
}
}
suc &= (x>=0);
cnt = nc;
}
if (suc && cnt<=mid) hi = mid;
else lo = mid+1;
}
cout << lo << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |