oj.uz

Submission #51724

# Submission time Handle Problem Language Result Execution time Memory
51724 2018-06-20T10:24:25 Z Milki Torrent (COI16_torrent) C++14
0 / 100
 680 ms 21632 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;

vector <int> edge[MAXN];
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;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
}

int par[MAXN];

void find_path(int x){

    for(auto it : edge[x]){
        if(it == par[x]) continue;
        par[it] = x;
        find_path(it);
    }
}

vector <int> path;

void create_path(){
    for(int i = b; i != a; i = par[i])
        path.push_back(i);
}

int cutEdge;

int calc(int curr, int par = 0){

    vector <int> v;
    for(auto it : edge[curr]){
        if(it == par) continue;
        if(it == cutEdge) continue;
        if(it == a || it == b) continue;
        v.push_back(calc(it, curr));
    }

    int ret = 0;
    sort(v.rbegin(), v.rend());
    REP(i, (int)v.size()){
        ret = max(ret, v[i] + i + 1);
    }
    //cout << "cvor " << curr << " f(cvor) = " << ret << "\n";
    return ret;
}

void solve(){
    int lo = 0, hi = path.size() - 1;
    int last = 0;

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

        int left = calc(a);
        int right = calc(b);
        if(left < right){
            lo = mid + 1;
            last = mid;
        }
        else
            hi = mid;
    }
    //TRACE(lo); TRACE(last);
    cutEdge = path[last];
    //TRACE(cutEdge);
    int sol = max(calc(a), calc(b));
    //cout << "\n\n";
    //calc(a);
    /*REP(i, path.size()){
        cout << "\n\n";
        TRACE(path[i]);
        cutEdge = path[i];
        TRACE(max(calc(a), calc(b)));
    } */
    if(last + 1 < path.size()){
        cutEdge = path[last + 1];
        //TRACE(cutEdge);
        sol = min(sol, max(calc(a), calc(b)));
    }

    cout << sol;
}

int main(){
    load();
    find_path(a);
    create_path();
    solve();
}

Compilation message

torrent.cpp: In function 'void solve()':
torrent.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(last + 1 < path.size()){
        ~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 69.0

# Verdict Execution time Memory Grader output
1 Incorrect 680 ms 21632 KB Output isn't correct
2 Halted 0 ms 0 KB -