Submission #743623

#	Time	Username	Problem	Language	Result	Execution time	Memory
743623		Lukap	Torrent (COI16_torrent)	C++14	0 / 100	237 ms	524288 KiB

torrent

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 7;

int a,b,n;
vector<int> susjedi[MAXN], path;
int cost[MAXN];
vector<pair<int, int> > vek;
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;
        }
    }
}

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 ts () {
    int lo = 0, hi = vek.size() - 1;

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

        if (solve (mid) < solve (mid + 1)) hi = mid;
        else lo = mid + 1;
    }

    return solve (lo);
}

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);
    for (int i = 0; i < path.size () - 1; i++) vek.push_back({path[i], path[i + 1]});

    cout << ts ();

    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < path.size () - 1; i++) vek.push_back({path[i], path[i + 1]});
      |                     ~~^~~~~~~~~~~~~~~~~~
torrent.cpp: In function 'bool put(int, int, int)':
torrent.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69