oj.uz

Submission #553689

# Submission time Handle Problem Language Result Execution time Memory
553689 2022-04-26T15:46:36 Z Alexandruabcde Torrent (COI16_torrent) C++14
100 / 100
 399 ms 28804 KB 
#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

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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7376 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 25624 KB Output is correct
2 Correct 390 ms 26996 KB Output is correct
3 Correct 392 ms 28520 KB Output is correct
4 Correct 399 ms 27852 KB Output is correct
5 Correct 375 ms 25224 KB Output is correct
6 Correct 337 ms 25680 KB Output is correct
7 Correct 361 ms 28804 KB Output is correct