Submission #915440

#	Time	Username	Problem	Language	Result	Execution time	Memory
915440		LeaRouse	Torrent (COI16_torrent)	C++14	100 / 100	381 ms	28868 KiB

torrent

//IOI - EGOI - OII 2024
//#pragma GCC optimize("Ofast") 
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
using namespace std;
const int MAX=3e5+5;
const int INF=1e9+5;
int A[MAX];
int dp[MAX];
vector<int>v[MAX];
vector<int>w;
int n,a,b;

void dfs(int u,int p){
    A[u]=p;
    for(int it:v[u]){
        if(p==it) continue;
        dfs(it,u);
    }
}
 
void dfs_1(int u,int p,int ab){
    vector<int> s;
    for(int it:v[u]){
        if(it==p or it==ab) continue;
        dfs_1(it,u,ab);
        s.push_back(dp[it]);
    }
    sort(s.begin(),s.end());
    for(int i=0;i<s.size();i++){
        dp[u]=max(dp[u],s[i]+int(s.size())-i);
    }
}

void go(){
    cin>>n>>a>>b;
    for(int i=0;i<n-1;i++){
        int a,b; cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs(a,a);
    w.push_back(b);
    while(w.back()!=a){
        w.push_back(A[w.back()]);
    }
    int l=0,r=int(w.size())-2;
    int ans=1e9+5;
    while(l<=r){
        fill(dp,dp+n+1,0);
        int mid=(l+r)/2;
        dfs_1(a,a,w[mid]);
        dfs_1(b,b,w[mid+1]);
        ans=min(ans,max(dp[a],dp[b]));
        if(dp[a]<dp[b]){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<ans<<endl;
}

int main(){
    fastio;
    go();
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs_1(int, int, int)':
torrent.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

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