Submission #1124255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124255		nikd	Torrent (COI16_torrent)	C++20	100 / 100	403 ms	27028 KiB

torrent

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> tree;
vector<int> path;

bool pth(int v, int p, int x){
    if(v == x){
        path.push_back(v); return 1;
    }
    for(int u: tree[v]){
        if(u==p) continue;
        if(pth(u, v, x)){
            path.push_back(v);
            return 1;
        }
    }
    return 0;
}


int dfs(int p,int n, int ev)
{
    int m=0;
    vector<int> v;
    for(auto c:tree[n])
    {   
        if(c==ev) continue;
        if(c!=p)
        {
            int a=dfs(n,c, ev);
            v.push_back(a);
        }
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        m=max(m,v[i]+i+1);
    }
    return m;
}

int trasferisci(int N, int R, int S, vector<int> U, vector<int> V) {
    tree.resize(N);

    for(int i=0;i<N-1;i++)
    {
        tree[U[i]].push_back(V[i]);
        tree[V[i]].push_back(U[i]);
    }

    if(S== R) return dfs(-1,S, -1);
    pth(S, -1, R);
    //for(int i: path) cout << i << ' '; cout << '\n';
    int l = 0; int r = path.size()-2;
    while(r-l>1){
        int m = (l+r)/2;
        int sls = dfs(-1, S, path[m]);
        int slr = dfs(-1, R, path[m+1]);
        if(sls>slr) l = m;
        else if(sls == slr) return sls;
        else r = m;
    }
    return min(max(dfs(-1, S, path[l]), dfs(-1, R,path[l+1])), max(dfs(-1, S, path[r]), dfs(-1, R,path[r+1])));
    
}
int main () {
    int N, R, S;
    cin >> N >> R >> S;
    R--; S--;

    vector<int> U(N - 1), V(N - 1);
    for (int i = 0; i < N - 1; i++){
        cin >> U[i] >> V[i];
        U[i]--; V[i]--;
    }

    cout << trasferisci(N, R, S, U, V) << "\n";
}

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