# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
952465 |
2024-03-24T03:20:37 Z |
vjudge1 |
Torrent (COI16_torrent) |
C++17 |
|
351 ms |
51832 KB |
#include<bits/stdc++.h>
using namespace std;
#define N 1<<20
vector<int>adj[N],path;
int dp[N],par[N],a,b,cut,ans=1e9;
void BT(int n){
for(auto i:adj[n])
if(i-par[n])
par[i]=n,BT(i);
}
void dfs(int n,int p){
dp[n]=0;
vector<int>kirby;
for(auto i:adj[n]) if(i-p&&i-cut)
dfs(i,n),kirby.push_back(dp[i]);
sort(kirby.rbegin(),kirby.rend());
for(int i=0;i<kirby.size();i++)
dp[n]=max(dp[n],kirby[i]+i+1);
}
bool check(int x,int y){
cut=x;
dfs(a,0);
cut=y;
dfs(b,0);
ans=min(ans,max(dp[a],dp[b]));
return dp[a]<dp[b];
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n;
cin>>n>>a>>b;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
BT(a);
dfs(a,0);
ans=dp[a];
if(a==b){
cout<<ans;
exit(0);
}
int b2=b;
while(b2-a)
path.push_back(b2),b2=par[b2];
path.push_back(a);
int l=0,r=path.size()-2;
while(l<=r){
int mid=l+r>>1;
if(check(path[mid],path[mid+1]))
l=mid+1;
else r=mid-1;
}
cout<<ans;
}
Compilation message
torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i=0;i<kirby.size();i++)
| ~^~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:51:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid=l+r>>1;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
29020 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
349 ms |
44552 KB |
Output is correct |
2 |
Correct |
351 ms |
46428 KB |
Output is correct |
3 |
Correct |
300 ms |
50284 KB |
Output is correct |
4 |
Correct |
309 ms |
47296 KB |
Output is correct |
5 |
Correct |
269 ms |
44108 KB |
Output is correct |
6 |
Correct |
262 ms |
45056 KB |
Output is correct |
7 |
Correct |
274 ms |
51832 KB |
Output is correct |