oj.uz

Submission #952439

# Submission time Handle Problem Language Result Execution time Memory
952439 2024-03-23T22:35:58 Z Error42 Power Plant (JOI20_power) C++17
0 / 100
 1 ms 348 KB 
#include <iostream>
#include <vector>

using namespace std;

int n;
vector<vector<int>> graph;
vector<bool> removed;
vector<int> subtree_sz;
vector<bool> generator;

void calc_subtree_sz(int const cur, int const par) {
    subtree_sz[cur] = 1;

    for (int const& neigh : graph[cur]) {
        if (neigh == par || removed[neigh])
            continue;

        calc_subtree_sz(neigh, cur);
        subtree_sz[cur] += subtree_sz[neigh];
    }
}

int find_centroid(int const cur, int const par, int const tree_sz) {
    for (int const& neigh : graph[cur]) {
        if (neigh == par || removed[neigh])
            continue;

        if (subtree_sz[neigh] > tree_sz / 2)
            return find_centroid(neigh, cur, tree_sz);
    }

    return cur;
}

int calc_ans_rec(int const cur, int const par) {
    int ans = -generator[cur];

    for (int const neigh : graph[cur]) {
        if (neigh == par || removed[neigh])
            continue;

        ans += calc_ans_rec(neigh, cur);
    }

    ans = max(ans, (int)generator[cur]);

    return ans;
}

int calc_ans(int const centroid) {
    return calc_ans_rec(centroid, -1);
}

int decomp(int const cur) {
    calc_subtree_sz(cur, -1);
    int const centroid = find_centroid(cur, -1, subtree_sz[cur]);

    int ans = calc_ans(centroid);

    removed[centroid] = true;

    for (int const neigh : graph[centroid]) {
        if (removed[neigh])
            continue;

        ans = max(ans, decomp(neigh));
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    graph.resize(n);
    removed.resize(n);
    subtree_sz.resize(n);
    generator.resize(n);

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    string s;
    cin >> s;

    for (int i = 0; i < n; i++)
        generator[i] = s[i] == '1';

    int const ans = decomp(0);

    cout << ans << "\n";
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -