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>
#define ll long long
#define pb push_back
#define mem(x, y) memset(& x, y, sizeof(x))
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cerr if(dbg)cerr
using namespace std;
bool dbg=1;
const int n0=3e5+123;
int n,a,b,dp[n0],good[n0];
vector<int> g[n0],path;
void dfs(int v,int p) {
if(v==b) {
good[v]=1;
}
vector<int> ord;
for(int to:g[v]) {
if(to==p) continue;
dfs(to,v);
good[v]|=good[to];
if(!good[to]) {
ord.pb(dp[to]+1);
}
}
sort(all(ord)),reverse(all(ord));
for(int i=0; i<SZ(ord); i++)
dp[v]=max(dp[v],ord[i]+i);
if(good[v]) {
path.pb(v);
}
}
int ok[n0];
bool check(int x) {
mem(ok,0);
int cur=0;
for(int i=0; i<SZ(path); i++) {
if(cur+dp[path[i]]+1<=x) cur++,ok[i]=1;
else if(cur+dp[path[i]]<=x) cur+=2,ok[i]=1;
else cur+=2;
}
cur=0;
for(int i=SZ(path)-1; i>=0; i--) {
if(cur+dp[path[i]]+1<=x) cur++,ok[i]=1;
else if(cur+dp[path[i]]<=x) cur+=2,ok[i]=1;
else cur+=2;
if(!ok[i]) return 0;
}
return 1;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> a >> b;
for(int i=1; i<n; i++) {
int x,y;cin >> x >> y;
g[x].pb(y),g[y].pb(x);
}
dfs(a,0);
assert(SZ(path)>1);
//for(int i=0; i<SZ(path); i++) {
//cerr << "path[" << i << "]=" << path[i] << "," << dp[path[i]] << '\n';
//}
int l=-1,r=n0;
while(l<r-1) {
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid;
}
cout << r;
}
Compilation message (stderr)
torrent.cpp: In function 'int main()':
torrent.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int mid=l+r>>1;
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |