oj.uz

Submission #391522

# Submission time Handle Problem Language Result Execution time Memory
391522 2021-04-19T07:28:36 Z palilo Dynamite (POI11_dyn) C++17
30 / 100
 702 ms 25008 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;

    vector<bool> d(n);
    for (auto&& x : d) {
        char c;
        cin >> c;
        x = c == '1';
    }

    if (count(d.begin(), d.end(), true) <= m)
        return cout << 0, 0;

    vector<vector<int>> adj(n);
    for (int i = n - 1, u, v; i--;) {
        cin >> u >> v, --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    auto rev_dfn = [&](int src) {
        vector<int> stk = {src}, vtx(n);

        for (int i = 0; i < n; ++i) {
            const auto u = stk.back();
            stk.pop_back();

            vtx[i] = u;
            for (const auto& v : adj[u]) {
                adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
                stk.emplace_back(v);
            }
        }
        reverse(vtx.begin(), vtx.end());
        return vtx;
    }(0);

    vector<int> dp_dyn(n), dp_fus(n);
    // dp_dyn[i] : maximum distance from i to dynamite in sub[i]
    // dp_fus[i] : minimum distance from i to   fuse   in sub[i]

    auto valid = [&](int lim) {
        fill(dp_dyn.begin(), dp_dyn.end(), -1);
        fill(dp_fus.begin(), dp_fus.end(), 0x3f3f3f3f);
        int k = m;

        for (const auto& u : rev_dfn) {
            for (const auto& v : adj[u]) {
                if (~dp_dyn[v]) dp_dyn[u] = max(dp_dyn[u], dp_dyn[v] + 1);
                dp_fus[u] = min(dp_fus[u], dp_fus[v] + 1);
            }
            if (dp_dyn[u] == -1 && d[u]) dp_dyn[u] = 0;

            if (dp_dyn[u] == lim) {
                if (!k--) return false;
                dp_dyn[u] = -1, dp_fus[u] = 0;
            } else if (dp_dyn[u] + dp_fus[u] <= lim)
                dp_dyn[u] = -1;
        }
        return true;
    };

    int lo = 1, hi = n - 1;
    while (lo != hi) {
        int mid = (lo + hi) >> 1;
        valid(mid) ? hi = mid : lo = mid + 1;
    }
    cout << lo;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1072 KB Output is correct
2 Correct 18 ms 2120 KB Output is correct
3 Correct 21 ms 2612 KB Output is correct
4 Correct 20 ms 2636 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4548 KB Output is correct
2 Correct 61 ms 6108 KB Output is correct
3 Correct 97 ms 6812 KB Output is correct
4 Incorrect 78 ms 6596 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 8500 KB Output is correct
2 Correct 100 ms 8600 KB Output is correct
3 Correct 113 ms 8472 KB Output is correct
4 Incorrect 129 ms 9264 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 16712 KB Output is correct
2 Correct 391 ms 19804 KB Output is correct
3 Incorrect 589 ms 20820 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 702 ms 25008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 675 ms 24824 KB Output isn't correct
2 Halted 0 ms 0 KB -