Submission #708367

#	Time	Username	Problem	Language	Result	Execution time	Memory
708367		Cyanmond	Power Plant (JOI20_power)	C++17	0 / 100	1 ms	296 KiB

power

#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));
    };

    for (int i = 0; i < N; ++i) calcDp(i);
    std::cout << answer << std::endl;

    /*

    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 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53