제출 #1170280

#제출 시각아이디문제언어결과실행 시간메모리
1170280JovicaTorrent (COI16_torrent)C++20
69 / 100
422 ms23956 KiB
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+1;
int n,A,B;
int depth[maxn];
vector<vector<int> > adj(maxn);
vector<int> pat;
bool pripagja[maxn];
int dp[maxn];

bool dfs(int p,int pret)
{
    pat.push_back(p);
    if (p == B) return true;
    for (auto a: adj[p]){
        if (a != pret && dfs(a,p)) return true;
    }
    pat.pop_back();
    return false;
}

int zab;

int f(int p,int pret)
{
    if (adj[p].size() == 1 && adj[p][0] == pret) return 0;
    if (pripagja[p]==false && dp[p]>0) return dp[p];
    vector<int> v;
    for (auto s: adj[p]){
        if (s == pret || (p == pat[zab] && s == pat[zab+1]) || (p == pat[zab+1] && s == pat[zab])) continue;
        v.push_back(f(s,p));
    }
    sort(v.begin(),v.end());reverse(v.begin(),v.end());

    int ans = 0;
    for (int i=0; i <v.size();i++) ans = max(ans,v[i]+i+1);

    //cout<<endl<<p<<" vrakja "<<ans<<endl;
    dp[p] = ans;
    return ans;
}

int ts(int l,int r)
{
    //cout<<l<< " "<<r<<endl;
    if (l >= r) return r;
    if (r - l < 3)
    {
        int p = 0,ans = 1e7;
        for (int i=l;i<=r;i++){
            zab = i;
            int x = max(f(A,0),f(B,0));
            if (x<ans){
                ans = x;
                p = i;
            }
        }
        return p;
    }
    int ml = l + (r-l)/3;
    int mr = r - (r-l)/3;
    zab = ml;
    int op1 = max(f(A,0), f(B,0));
    zab = mr;
    int op2 = max(f(A,0), f(B,0));

    if (op1<op2) return ts(l,mr);
    else return ts(ml,r);
}

int main()
{
    cin>>n>>A>>B;
    for (int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(A,0);
    //for (auto a: pat) cout<<a<<" ";
    for (auto a: pat) pripagja[a] = true;

    int ans = 1e7;
    if (pat.size()<= 5){
        for (int i=0;i<pat.size()-1;i++){
            //zab = ts(0,pat.size()-1);
            zab = i;
            int x = f(A,0),y = f(B,0);
            ans = min(ans,max(x,y));
            //cout<<"x = "<<x<<" y="<<y<<endl;
        }
        cout<<ans;
        return 0;
    }

    zab = ts(0,pat.size()-2);
    cout<<max(f(A,0),f(B,0))<<endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...