oj.uz

Submission #569495

# Submission time Handle Problem Language Result Execution time Memory
569495 2022-05-27T12:32:10 Z Waratpp123 Torrent (COI16_torrent) C++14
100 / 100
 469 ms 28804 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> g[300010],tr;
int a,b,par[300010],mark[300010],dp[300010];
int dfs1(int i,int p){
    if(i==b) return 1;
    for(auto x : g[i]){
        if(x==p) continue;
        int opr=dfs1(x,i);
        if(opr==1){
            tr.push_back(x);
            return 1;
        }
    }
    return 0;
}
void setpar(int i,int p){
    par[i]=p;
    for(auto x : g[i]){
        if(x==p) continue;
        setpar(x,i);
    }
}
int dfs(int i,int p){
    vector<int> t;
    t.clear();
    for(auto x : g[i]){
        if(x==p||mark[x]==1) continue;
        dfs(x,i);
        t.push_back(dp[x]);
    }
    int mx=0,n=t.size();
    sort(t.begin(),t.end());
    for(int j=0;j<n;j++){
        mx=max(mx,t[j]+(n-j));
    }
    return dp[i]=mx;
}
int main(){
    int i,j,n,u,v;
    scanf("%d %d %d",&n,&a,&b);
    for(i=1;i<=n-1;i++){
        scanf("%d %d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(a,-1);
    setpar(a,-1);
    int l=-1,r=tr.size()-1,mid;
    while(l<r){
        mid=(l+r+1)/2;
        mark[tr[mid]]=1;
        int suma=dfs(a,-1);
        mark[tr[mid]]=0;
        mark[par[tr[mid]]]=1;
        int sumb=dfs(b,-1);
        mark[par[tr[mid]]]=0;
        if(suma<sumb) r=mid-1;
        else l=mid;
    }
    int ans;
        mark[tr[l]]=1;
        int suma=dfs(a,-1);
        mark[tr[l]]=0;
        mark[par[tr[l]]]=1;
        int sumb=dfs(b,-1);
        mark[par[tr[l]]]=0;
    ans=max(suma,sumb);
    if(l<tr.size()-1){
        mark[tr[l+1]]=1;
        suma=dfs(a,-1);
        mark[tr[l+1]]=0;
        mark[par[tr[l+1]]]=1;
        sumb=dfs(b,-1);
        mark[par[tr[l+1]]]=0;
        ans=min(ans,max(suma,sumb));
    }
    printf("%d\n",ans);
return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:69:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     if(l<tr.size()-1){
      |        ~^~~~~~~~~~~~
torrent.cpp:40:11: warning: unused variable 'j' [-Wunused-variable]
   40 |     int i,j,n,u,v;
      |           ^
torrent.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d %d %d",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
torrent.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7360 KB Output is correct
2 Correct 6 ms 7360 KB Output is correct
3 Correct 6 ms 7380 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 25616 KB Output is correct
2 Correct 467 ms 26976 KB Output is correct
3 Correct 446 ms 28428 KB Output is correct
4 Correct 469 ms 27856 KB Output is correct
5 Correct 439 ms 25204 KB Output is correct
6 Correct 411 ms 25676 KB Output is correct
7 Correct 430 ms 28804 KB Output is correct