# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
952470 |
2024-03-24T03:30:44 Z |
vjudge1 |
Torrent (COI16_torrent) |
C++17 |
|
377 ms |
29360 KB |
#include<bits/stdc++.h>
using namespace std;
#define N 5<<16
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){
cut=x;
dfs(a,0);
cut=par[x];
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];
int b2=b;
while(b2-a)
path.push_back(b2),b2=par[b2];
if(n<=1000){
for(auto i:path)
check(i);
cout<<ans;
return 0;
}
int l=0,r=path.size()-1;
while(l<=r){
int mid=l+r>>1;
if(check(path[mid]))
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:52:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid=l+r>>1;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
10588 KB |
Output is correct |
2 |
Correct |
6 ms |
10544 KB |
Output is correct |
3 |
Correct |
7 ms |
10584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
290 ms |
23024 KB |
Output is correct |
2 |
Correct |
377 ms |
24964 KB |
Output is correct |
3 |
Correct |
283 ms |
27704 KB |
Output is correct |
4 |
Correct |
343 ms |
25684 KB |
Output is correct |
5 |
Correct |
268 ms |
22480 KB |
Output is correct |
6 |
Correct |
240 ms |
23252 KB |
Output is correct |
7 |
Correct |
300 ms |
29360 KB |
Output is correct |