oj.uz

Submission #1113758

# Submission time Handle Problem Language Result Execution time Memory
1113758 2024-11-17T10:46:20 Z 0pt1mus23 Torrent (COI16_torrent) C++14
100 / 100
 437 ms 29956 KB 
// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 3e5 +23, inf = LLONG_MAX, LG = 20;
int par[sze];
vector<int> graph[sze];

void dfs(int node,int p=-1){
    par[node]=p;
    for(auto v:graph[node]){
        if(v!=p){
            dfs(v,node);
        }
    }
}
pair<int,int> edge;
int dfs2(int node,int p=-1){
    int sum=0;
    vector<int> lst;
    // cout<<node<<" "<<p<<" "<<edge.first<<" "<<edge.second<<endl;
    for(auto v:graph[node]){
        // to = make_pair(min(node,v),max(node,v));
        if(v!=p && edge!=make_pair(min(node,v),max(node,v))){
            lst.pb(dfs2(v,node));
        }
    }
    sort(all(lst),greater<int>());
    for(int i=1;i<=lst.size();i++){
        sum=max(sum,lst[i-1]+i);
    }
    return sum;
}

void fast(){
    int n,va,vb;
    cin>>n>>va>>vb;
    vector<int> yol;
    for(int i =1;i<n;i++){
        int u,v;
        cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    dfs(va);
    for(int node= vb;node!=va;node = par[node]){
        yol.pb(node);
    }
    // for(auto v:yol)cout<<v<<" ";cout<<endl;
    int l =0;
    int r = yol.size()-1;
    int best = 0;
    while(l<=r){
        int mid = (l+r)/2;
        edge = make_pair( min(yol[mid],par[yol[mid]]), max(yol[mid],par[yol[mid]])); 
        int a= dfs2(va);
        int b = dfs2(vb);
        if(a-b >= 0){
            best= mid;
            l = mid+1;
        }
        else{
            r = mid-1;
        }
    }
    // cout<<best<<" : "<<yol[best]<<" "<<par[yol[best]]<<endl;
    int ans = inf;
    
    for(int j=best-1;j<=best+1;j++){
        if(j>=0 && j<yol.size()){
            edge = make_pair( min(yol[j],par[yol[j]]), max(yol[j],par[yol[j]])); 
            ans= min(ans,max(dfs2(va),dfs2(vb)));
        }
    }
    assert(ans<inf);
    putr(ans);
}
 
signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

Compilation message

torrent.cpp: In function 'long long int dfs2(long long int, long long int)':
torrent.cpp:35:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=1;i<=lst.size();i++){
      |                 ~^~~~~~~~~~~~
torrent.cpp: In function 'void fast()':
torrent.cpp:76:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if(j>=0 && j<yol.size()){
      |                    ~^~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 3 ms 8888 KB Output is correct
3 Correct 5 ms 8784 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 22856 KB Output is correct
2 Correct 366 ms 28104 KB Output is correct
3 Correct 379 ms 29308 KB Output is correct
4 Correct 386 ms 28872 KB Output is correct
5 Correct 417 ms 26400 KB Output is correct
6 Correct 437 ms 27104 KB Output is correct
7 Correct 377 ms 29956 KB Output is correct