oj.uz

Submission #51740

# Submission time Handle Problem Language Result Execution time Memory
51740 2018-06-20T16:23:12 Z Milki Torrent (COI16_torrent) C++14
100 / 100
 810 ms 48280 KB 
#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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7524 KB Output is correct
3 Correct 10 ms 7524 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 20716 KB Output is correct
2 Correct 666 ms 25996 KB Output is correct
3 Correct 663 ms 31376 KB Output is correct
4 Correct 663 ms 34876 KB Output is correct
5 Correct 657 ms 36460 KB Output is correct
6 Correct 596 ms 41436 KB Output is correct
7 Correct 572 ms 48280 KB Output is correct