oj.uz

Submission #384982

# Submission time Handle Problem Language Result Execution time Memory
384982 2021-04-02T19:39:42 Z dolphingarlic Torrent (COI16_torrent) C++14
100 / 100
 150 ms 33896 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, a, b, dp[300001];
vector<int> graph[300001], chain, chain_cdp[300001];
bool on_chain[300001], good[300001];

bool find_chain(int node = a, int parent = 0) {
    if (node == b) {
        chain.push_back(node);
        on_chain[node] = true;
        return true;
    }
    for (int i : graph[node]) if (i != parent && find_chain(i, node)) {
        chain.push_back(node);
        on_chain[node] = true;
        return true;
    }
    return false;
}

void calc_dp(int node, int parent = 0) {
    vector<int> cdp;
    for (int i : graph[node]) if (i != parent && !on_chain[i]) {
        calc_dp(i, node);
        cdp.push_back(dp[i]);
    }
    sort(cdp.begin(), cdp.end(), greater<int>());
    for (int i = 0; i < cdp.size(); i++) {
        cdp[i] += i + 1;
        dp[node] = max(dp[node], cdp[i]);
    }
    if (on_chain[node]) {
        for (int i = cdp.size() - 2; i >= 0; i--) cdp[i] = max(cdp[i], cdp[i + 1]);
        chain_cdp[node] = cdp;
    }
}

bool check(int pot) {
    for (int i : chain) good[i] = false;

    for (int _ : {0, 1}) {
        int curr_time = 0;
        for (int i : chain) {
            good[i] |= (curr_time + dp[i] <= pot);
            int delta;
            for (delta = 0; delta < chain_cdp[i].size(); delta++) {
                if (curr_time + chain_cdp[i][delta] < pot) break;
            }
            curr_time += delta + 1;
        }
        reverse(chain.begin(), chain.end());
    }

    bool res = true;
    for (int i : chain) res &= good[i];
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> a >> b;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    find_chain();
    for (int i : chain) calc_dp(i);

    int l = 0, r = n;
    while (l != r) {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}

Compilation message

torrent.cpp: In function 'void calc_dp(int, int)':
torrent.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < cdp.size(); i++) {
      |                     ~~^~~~~~~~~~~~
torrent.cpp: In function 'bool check(int)':
torrent.cpp:48:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for (delta = 0; delta < chain_cdp[i].size(); delta++) {
      |                             ~~~~~~^~~~~~~~~~~~~~~~~~~~~
torrent.cpp:43:14: warning: unused variable '_' [-Wunused-variable]
   43 |     for (int _ : {0, 1}) {
      |              ^

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14444 KB Output is correct
2 Correct 11 ms 14572 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 31360 KB Output is correct
2 Correct 146 ms 32492 KB Output is correct
3 Correct 150 ms 33080 KB Output is correct
4 Correct 140 ms 33896 KB Output is correct
5 Correct 140 ms 31084 KB Output is correct
6 Correct 129 ms 31172 KB Output is correct
7 Correct 149 ms 33600 KB Output is correct