oj.uz

Submission #248964

# Submission time Handle Problem Language Result Execution time Memory
248964 2020-07-13T19:11:47 Z marlicu Torrent (COI16_torrent) C++14
100 / 100
 577 ms 29492 KB 
#include <bits/stdc++.h>

using namespace std;

#define _ << " "
#define pb push_back
#define X first
#define Y second

const int MAXN = 3e5 + 5;

int n, a, b, x, y;
vector <int> veze[MAXN];
int roditelj[MAXN];
int dp[MAXN];

void istrazi(int x) {
    for (int nx : veze[x]) {
        if (nx == roditelj[x]) continue;
        roditelj[nx] = x;
        istrazi(nx);
    }
}

int izracunaj(int x, int rodx, int p, int rodp) {
    dp[x] = 0;
    vector <int> djeca;

    for (int nx : veze[x]) {
        if (nx == rodx) continue;
        if (x == p && nx == rodp) continue;
        if (x == rodp && nx == p) continue;
        djeca.pb(izracunaj(nx, x, p, rodp));
    }

    sort (djeca.rbegin(), djeca.rend());
    for (int i = 0; i < djeca.size(); i++) {
        dp[x] = max(dp[x], djeca[i] + i + 1);
    }

    return dp[x];
}

int delta(int x) {
    int astrana = izracunaj(a, 0, x, roditelj[x]);
    int bstrana = izracunaj(b, 0, x, roditelj[x]);
    return astrana - bstrana;
}

int izracunaj2(int x) {
    int astrana = izracunaj(a, 0, x, roditelj[x]);
    int bstrana = izracunaj(b, 0, x, roditelj[x]);
    return max(astrana, bstrana);
}

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

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

    istrazi(a);

    vector <int> put;
    for (int i = b; i != a; i = roditelj[i]) put.pb(i);


    int lo = 0, hi = put.size() - 1, mid;
    while (lo < hi) {
        mid = (lo + hi) / 2;
        if (delta(put[mid]) > 0) lo = mid + 1;
        else hi = mid;
    }

    int rjesenje = izracunaj2(put[lo]);
    if (lo) rjesenje = min(rjesenje, izracunaj2(put[lo - 1]));
    if (lo + 1 < put.size()) rjesenje = min(rjesenje, izracunaj2(put[lo + 1]));

    cout << rjesenje << '\n';

    return 0;
}

Compilation message

torrent.cpp: In function 'int izracunaj(int, int, int, int)':
torrent.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < djeca.size(); i++) {
                     ~~^~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:82:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (lo + 1 < put.size()) rjesenje = min(rjesenje, izracunaj2(put[lo + 1]));
         ~~~~~~~^~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 25848 KB Output is correct
2 Correct 558 ms 27664 KB Output is correct
3 Correct 577 ms 29324 KB Output is correct
4 Correct 576 ms 28364 KB Output is correct
5 Correct 544 ms 25464 KB Output is correct
6 Correct 521 ms 26104 KB Output is correct
7 Correct 494 ms 29492 KB Output is correct