oj.uz

Submission #743649

# Submission time Handle Problem Language Result Execution time Memory
743649 2023-05-17T15:21:37 Z Lukap Torrent (COI16_torrent) C++14
100 / 100
 476 ms 33568 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5 + 7;

int a,b,n;
vector<int> susjedi[MAXN], path;
int cost[MAXN];
pair<int, int> obris;
vector<int> v[MAXN];

bool put (int x, int p, int y) {
    if (x == y) {
        path.push_back (x);
        return 1;
    }
    for (auto nx: susjedi[x]) {
        if (nx == p) continue;
        if (put (nx, x, y)) {
            path.push_back (x);
            return 1;
        }
    }
    return 0;
}

void dfs (int x, int p) {
    cost[x] = 0;
    for (auto nx: susjedi[x]) {
        if (nx == p) continue;
        if ((obris.first == x && obris.second == nx) || (obris.first == nx && obris.second == x)) continue;
        dfs (nx, x);
        v[x].push_back (cost[nx]);
    }
    sort (v[x].begin(), v[x].end ());
    int cnt = 1;
    for (int i = v[x].size () - 1; i >= 0; i--) {
        cost[x] = max (cost[x], v[x][i] + cnt);
        cnt++;
    }
}

void clean () {
    for (int i = 0; i < n; i++) v[i].clear ();
}

int solve (int k) {
    obris = {path[k], path[k + 1]};
    clean ();
    dfs (a, -1);
    dfs (b, -1);
    return max (cost[a], cost[b]);
}

int bs () {
    int lo = 0, hi = path.size() - 2;

    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        solve (mid);

        if (cost[a] == cost[b]) {
            lo = mid;
            break;
        }
        if (cost[b] < cost[a]) lo = mid;
        else hi = mid - 1;
    }

    int rj = solve (lo);
    if (lo > 0) rj = min (rj, solve (lo - 1));
    if (lo < path.size() - 2) rj = min (rj, solve (lo + 1));
    return rj;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie (0);

    cin >> n >> a >> b;
    a--;b--;

    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--;y--;
        susjedi[x].push_back (y);
        susjedi[y].push_back (x);
    }
    put (a, -1, b);

    cout << bs ();

    return 0;
}

Compilation message

torrent.cpp: In function 'int bs()':
torrent.cpp:73:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     if (lo < path.size() - 2) rj = min (rj, solve (lo + 1));
      |         ~~~^~~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 30760 KB Output is correct
2 Correct 459 ms 31820 KB Output is correct
3 Correct 416 ms 32628 KB Output is correct
4 Correct 370 ms 32840 KB Output is correct
5 Correct 409 ms 30872 KB Output is correct
6 Correct 363 ms 31220 KB Output is correct
7 Correct 327 ms 33568 KB Output is correct