Submission #51740

#	Time	Username	Problem	Language	Result	Execution time	Memory
51740		Milki	Torrent (COI16_torrent)	C++14	100 / 100	810 ms	48280 KiB

torrent

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

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 3e5 + 5;

struct edge{
    int to, id;
    edge(){};
    edge(int _to, int _id){
        to = _to; id = _id;
    }
};

vector <edge> E[MAXN];
vector <int> path, tmp;
int n, a, b;

void load(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> a >> b;
    REP(i, n - 1){
        int x, y; cin >> x >> y;
        E[x].push_back(edge(y, i));
        E[y].push_back(edge(x, i));
    }
}

void findPath(int x, int par = 0){
    if(path.size())
        return;

    if(x == b){
        path = tmp;
        return;
    }

    for(auto it : E[x]){
        if(it.to == par) continue;

        tmp.push_back(it.id);
        findPath(it.to, x);
        tmp.pop_back();
    }
}

int cutEdge;

int calc(int x, int par = 0){
    int ret = 0;
    vector <int> v;

    for(auto it : E[x]){
        if(it.to == par) continue;
        if(it.id == cutEdge) continue;
        v.push_back(calc(it.to, x));
    }

    sort(v.rbegin(), v.rend());
    REP(i, (int)v.size())
        ret = max(ret, v[i] + i + 1);

    return ret;
}

int main(){
    load();
    findPath(a);

    int lo = 0, hi = path.size() - 1;

    while(lo < hi){
        int mid = (lo + hi) >> 1;
        cutEdge = path[mid];

        int left = calc(a);
        int right = calc(b);

        if(left < right)
            lo = mid + 1;
        else
            hi = mid;
    }
    cutEdge = path[lo];
    int sol = max(calc(a), calc(b));

    if(lo - 1 >= 0){
        cutEdge = path[lo - 1];
        sol = min(sol, max(calc(a), calc(b)));
    }

    cout << sol;
}

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