oj.uz

Submission #520795

# Submission time Handle Problem Language Result Execution time Memory
520795 2022-01-31T04:40:30 Z krit3379 Torrent (COI16_torrent) C++17
100 / 100
 382 ms 27816 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 300005

int id[N],sz,ans=2e9;
vector<int> g[N];
bitset<N> in;

bool find_path(int s,int f,int e){
    if(s==e){
        id[s]=++sz;
        return in[s]=true;
    }
    for(auto x:g[s]){
        if(x==f)continue;
        if(find_path(x,s,e)){
            id[s]=++sz;
            return in[s]=true;
        }
    }
    return in[s];
}

int dfs1(int s,int f,int lim){
    int ma=0;
    vector<int> v;
    for(auto x:g[s]){
        if(x==f||id[x]>lim)continue;
        v.push_back(dfs1(x,s,lim));
    }
    sort(v.begin(),v.end(),greater<int>());
    for(int i=0;i<v.size();i++)ma=max(ma,v[i]+i+1);
    return ma;
}

int dfs2(int s,int f,int lim){
    int ma=0;
    vector<int> v;
    for(auto x:g[s]){
        if(x==f||(id[x]&&id[x]<=lim))continue;
        v.push_back(dfs2(x,s,lim));
    }
    sort(v.begin(),v.end(),greater<int>());
    for(int i=0;i<v.size();i++)ma=max(ma,v[i]+i+1);
    return ma;
}

int main(){
    int n,i,s1,s2,a,b,l,r,mid,val1,val2;
    scanf("%d %d %d",&n,&s1,&s2);
    for(i=1;i<n;i++){
        scanf("%d %d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    find_path(s2,0,s1);
    l=1,r=sz-1;
    while(l<=r){
        mid=(l+r)/2;
        val1=dfs1(s1,0,mid);
        val2=dfs2(s2,0,mid);
        ans=min(ans,max(val1,val2));
        if(val1>val2)r=mid-1;
        else l=mid+1;
    }
    printf("%d",ans);
    return 0;
}

Compilation message

torrent.cpp: In function 'int dfs1(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<v.size();i++)ma=max(ma,v[i]+i+1);
      |                 ~^~~~~~~~~
torrent.cpp: In function 'int dfs2(int, int, int)':
torrent.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<v.size();i++)ma=max(ma,v[i]+i+1);
      |                 ~^~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d %d %d",&n,&s1,&s2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7352 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 24220 KB Output is correct
2 Correct 345 ms 25920 KB Output is correct
3 Correct 363 ms 27008 KB Output is correct
4 Correct 382 ms 27604 KB Output is correct
5 Correct 366 ms 23768 KB Output is correct
6 Correct 325 ms 24284 KB Output is correct
7 Correct 318 ms 27816 KB Output is correct