oj.uz

Submission #404956

# Submission time Handle Problem Language Result Execution time Memory
404956 2021-05-15T11:56:01 Z _contender_ Torrent (COI16_torrent) C++14
100 / 100
 717 ms 43504 KB 
#include<bits/stdc++.h>
using namespace std;
int n , a ,b;
vector<int>v[1000001];
int par[1000001];
int n1 , n2;


int dfs1(int x , int p)
{
    vector<int>temp;
    for(int i =0 ; i < (int)v[x].size() ; i++)
    {
        if(v[x][i] == p || (x == n1 && v[x][i]== n2) || (x == n2 && v[x][i] == n1))
        {
           /* if(x == 1)
            cout << "pakda"<<  " " << n1 << " " << n2 << " " << x << " " << v[x][i] << " " << p << "\n";
            */
            continue;
        }
        temp.push_back(dfs1(v[x][i] , x));
    }
    int ans = 0;
    sort(temp.begin() , temp.end() , greater<int>());
   /* if(x == 1)
    {
        cout << "vector for node 1" << "\n";
        for(int i = 0 ; i < (int)temp.size() ; i++)
        cout << temp[i] <<  " ";
        
        cout << "\n";
    }*/
    for(int i = 0 ; i < (int)temp.size() ; i++)
    {
        ans = max(ans , temp[i] + i + 1);
    }
   // cout <<"dfs" << " " <<  x << " " << ans << "\n";
    return ans;
}


pair<int , int> calc(int x , int y)
{
    n1 = x , n2 = y;
    pair<int , int>ans;
    ans.first = dfs1(a , a);
    ans.second  = dfs1(b , b);
    return ans;
}



void dfs(int x , int p)
{
    par[x] = p;
    for(int i = 0; i < (int)v[x].size() ; i++)
    {
        if(v[x][i] == p)
        continue;
        dfs(v[x][i] , x);
    }
}
int main()
{
   
    cin >> n >> a >> b;
    
    
    for(int i = 0 ; i < n-1 ; i++)
    {
        int x , y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    
    dfs(a , a);
    
    vector<int>vec;
    vec.push_back(b);
    while(vec.back() != a)
    {
        vec.push_back(par[vec.back()]);   
    }
    reverse(vec.begin() , vec.end());
    
    int l = 0 , r = (int)vec.size()-2;
    //cout << l << " " << r << "\n";
    int pos = 0;
    while(l <= r)
    {
        int mid = (l+r)/2;
        pair<int ,int>pr = calc(vec[mid] , vec[mid+1]);
        if(pr.first <= pr.second)
        {
            pos = mid;
            l = mid+1;
        }
        else
        r = mid-1;
    }
    
    
    
    int ans = 1e9;
   // pos = 2;
   // cout << vec[2] << " "<< vec[3] << " " << "verify" << "\n";
    pair<int , int>p1 = calc(vec[pos] , vec[pos+1]);
   // cout << p1.first << " " << p1.second << "\n";
    ans = min(ans , max(p1.first , p1.second));
    if(pos+1 < (int)vec.size()-1)
    {
        pair<int , int>p2 = calc(vec[pos+1] , vec[pos+2]);
        ans = min(ans , max(p2.first , p2.second));
    }
    
    cout << ans;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23756 KB Output is correct
2 Correct 17 ms 23792 KB Output is correct
3 Correct 17 ms 23776 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 36548 KB Output is correct
2 Correct 682 ms 41772 KB Output is correct
3 Correct 663 ms 43084 KB Output is correct
4 Correct 657 ms 42680 KB Output is correct
5 Correct 633 ms 40144 KB Output is correct
6 Correct 606 ms 40672 KB Output is correct
7 Correct 585 ms 43504 KB Output is correct