Submission #248964

#	Time	Username	Problem	Language	Result	Execution time	Memory
248964		marlicu	Torrent (COI16_torrent)	C++14	100 / 100	577 ms	29492 KiB

torrent

#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 (stderr)

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 / 31
• Subtask 2: 69 / 69