oj.uz

Submission #51723

# Submission time Handle Problem Language Result Execution time Memory
51723 2018-06-20T09:23:26 Z Milki Torrent (COI16_torrent) C++14
0 / 100
 583 ms 25760 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;
        v.push_back(calc(it, curr));
    }

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

    return ret;
}

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

    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;
            last = mid;
        }
        else
            hi = mid - 1;
    }
    //TRACE(lo); TRACE(last);
    cutEdge = path[last];
    int sol = max(calc(a), calc(b));
    if(last + 1 < path.size()){
        cutEdge = path[last + 1];
        sol = min(sol, max(calc(a), calc(b)));
    }

    cout << sol - 1;
}

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

Compilation message

torrent.cpp: In function 'void solve()':
torrent.cpp:83: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 9 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 583 ms 25760 KB Output isn't correct
2 Halted 0 ms 0 KB -