oj.uz

Submission #708361

# Submission time Handle Problem Language Result Execution time Memory
708361 2023-03-11T15:55:26 Z Cyanmond Power Plant (JOI20_power) C++17
0 / 100
 1 ms 304 KB 
#include <bits/stdc++.h>

int main() {
    // centroid decomposition
    int N;
    std::cin >> N;
    std::vector<int> A(N - 1), B(N - 1);
    std::vector<std::vector<int>> Tree(N);
    for (int i = 0; i < N - 1; ++i) {
        std::cin >> A[i] >> B[i];
        --A[i], --B[i];
        Tree[A[i]].push_back(B[i]);
        Tree[B[i]].push_back(A[i]);
    }
    std::string S;
    std::cin >> S;

    std::vector<bool> isValid(N, true);
    std::vector<int> subtreeSize(N), dp(N);
    int answer = 0;

    auto calcDp = [&](const int root) {
        auto dfs = [&](auto &&self, const int v, const int p) -> int {
            dp[v] = (S[v] == '1' ? 1 : 0);
            int sum = 0;
            for (const int t : Tree[v]) {
                if (t == p or (not isValid[t])) continue;
                sum += self(self, t, v);
            }
            if (S[v] == '1') --sum;
            dp[v] = std::max(dp[v], sum);
            return dp[v];
        };
        answer = std::max(answer, dfs(dfs, root, -1));
    };

    auto centroidDecomposite = [&](auto &&self, const int root) -> void {
        // calc subtree size
        auto dfs1 = [&](auto &&self2, const int v, const int p) -> int {
            subtreeSize[v] = 1;
            for (const int t : Tree[v]) {
                if (t == p or (not isValid[t])) continue;
                subtreeSize[v] += self2(self2, t, v);
            }
            return subtreeSize[v];
        };
        dfs1(dfs1, root, -1);
        // find centroid
        const int mas = subtreeSize[root];
        auto dfs2 = [&](auto &&self2, const int v, const int p) -> int {
            bool isCentroid = true;
            for (const int t : Tree[v]) {
                if (t == p or (not isValid[t])) continue;
                const int res = self2(self2, t, v);
                if (res != -1) return res;
                if (subtreeSize[t] > mas / 2) isCentroid = false;
            }
            if ((mas - subtreeSize[v]) > mas/ 2) isCentroid = false;
            return isCentroid ? v : -1;
        };
        const int centroid = dfs2(dfs2, root, -1);

        // dp
        calcDp(centroid);

        // rec
        isValid[centroid] = false;
        for (const int t : Tree[centroid]) {
            if (isValid[t]) {
                self(self, t);
            }
        }
    };
    centroidDecomposite(centroidDecomposite, 0);
    std::cout << answer << std::endl;
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Incorrect 1 ms 212 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Incorrect 1 ms 212 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -