Submission #553689

#	Time	Username	Problem	Language	Result	Execution time	Memory
553689		Alexandruabcde	Torrent (COI16_torrent)	C++14	100 / 100	399 ms	28804 KiB

torrent

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 3e5 + 5;

int N, A, B;
vector <int> G[NMAX];
int dp[NMAX];
int Dad[NMAX];

bool blocked[NMAX];

void Dfs (int Node, int dad = 0) {
    Dad[Node] = dad;

    for (auto it : G[Node]) {
        if (it == dad) continue;

        Dfs(it, Node);
    }
}

void DoDp (int Node, int dad = -1) {
    vector <int> values;
    for (auto it : G[Node]) {
        if (it == dad || blocked[it]) continue;

        DoDp(it, Node);
        values.push_back(dp[it]);
    }

    if (values.empty()) {
        dp[Node] = 0;
        return;
    }

    sort(values.begin(), values.end());
    for (int i = 0; i < values.size(); ++ i )
        values[i] += (values.size()-i);

    dp[Node] = values[0];
    for (int i = 1; i < values.size(); ++ i )
        dp[Node] = max(dp[Node], values[i]);
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> A >> B;

    for (int i = 1; i < N; ++ i ) {
        int x, y;
        cin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }
}

vector <int> Order;

void Precompute () {
    Dfs(A);

    for (int i = B; i != A; i = Dad[i])
        Order.push_back(i);
}

int Value (int Nod) {
    blocked[Nod] = 1;
    DoDp(A);
    blocked[Nod] = 0;

    blocked[Dad[Nod]] = 1;
    DoDp(B);
    blocked[Dad[Nod]] = 0;

    return (dp[A] - dp[B]);
}

void Solve () {
    int st = 0, dr = Order.size()-1;
    int ans = N;
    /// B Dad[B] Dad[Dad[B]] ... A

    while (st <= dr) {
        int mij = (st + dr) / 2;

        int val = Value(Order[mij]);
        ///dp[A] >= dp[B]
        if (val > 0) {
            ans = min(ans, max(dp[A], dp[B]));
            st = mij + 1;
        }
        else {
            ans = min(ans, max(dp[A], dp[B]));
            dr = mij - 1;
        }
    }

    cout << ans << '\n';
}

int main () {
    Read();

    Precompute();

    Solve();

    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void DoDp(int, int)':
torrent.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < values.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~~
torrent.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 1; i < values.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~~

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