Submission #1170257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170257		Jovica	Torrent (COI16_torrent)	C++20	31 / 100	2095 ms	21748 KiB

torrent

#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;
    int ml = (l+l+r)/3;
    int mr = (l+r+r)/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(ml+1,r);
    else return ts(l,mr-1);
}

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;
    for (int i=0;i<pat.size()-1;i++){
        //zab = ts(0,pat.size()-1);
        zab = i;
//        cout<<"zabraneto e "<<
        int x = f(A,0),y = f(B,0);
        ans = min(ans,max(x,y));
        //cout<<"x = "<<x<<" y="<<y<<endl;
    }
    cout<<ans;

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

    return 0;
}

• Subtask 1: 31 / 31
• Subtask 2: 0 / 69