oj.uz

Submission #915440

# Submission time Handle Problem Language Result Execution time Memory
915440 2024-01-23T22:53:06 Z LeaRouse Torrent (COI16_torrent) C++14
100 / 100
 381 ms 28868 KB 
//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

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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8956 KB Output is correct
2 Correct 4 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 25660 KB Output is correct
2 Correct 381 ms 27152 KB Output is correct
3 Correct 284 ms 28544 KB Output is correct
4 Correct 323 ms 27976 KB Output is correct
5 Correct 290 ms 25292 KB Output is correct
6 Correct 267 ms 25776 KB Output is correct
7 Correct 275 ms 28868 KB Output is correct