Submission #952800

#	Time	Username	Problem	Language	Result	Execution time	Memory
952800		boyliguanhan	Torrent (COI16_torrent)	C++17	100 / 100	312 ms	33472 KiB

torrent

#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 (stderr)

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;
      |                 ~^~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69