Submission #702333

#	Time	Username	Problem	Language	Result	Execution time	Memory
702333		Cyanmond	Spring cleaning (CEOI20_cleaning)	C++17	34 / 100	1088 ms	20732 KiB

cleaning

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N - 1), B(N - 1);
    std::vector<std::vector<int>> baseTree(N);
    for (int i = 0; i < N - 1; ++i) {
        std::cin >> A[i] >> B[i];
        --A[i], --B[i];
        baseTree[A[i]].push_back(B[i]);
        baseTree[B[i]].push_back(A[i]);
    }
    std::vector<int> D(Q);
    std::vector<std::vector<int>> L(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> D[i];
        L[i].resize(D[i]);
        for (int &e : L[i]) {
            std::cin >> e;
            --e;
        }
    }
    std::vector<int> degree(N);
    for (int i = 0; i < N; ++i) {
        degree[i] = (int)baseTree[i].size();
    }
    const int nonLeafV = (std::max_element(degree.begin(), degree.end()) - degree.begin());

    for (int q = 0; q < Q; ++q) {
        std::vector<std::vector<int>> tree = baseTree;
        for (int i = 0; i < D[q]; ++i) {
            const int v = L[q][i];
            tree.push_back(std::vector<int>());
            tree[N + i].push_back(v);
            tree[v].push_back(N + i);
        }

        auto dfs = [&](auto &&self, const int v, const int p) -> std::pair<i64, int> {
            i64 ret = 0;
            int cnt = 0;
            if (tree[v].size() == 1) {
                ret = 0;
                cnt = 1;
                return {ret, cnt};
            }
            for (const int t : tree[v]) {
                if (p == t) {
                    continue;
                }
                const auto [cval, c] = self(self, t, v);
                assert(1 <= c and c <= 2);
                cnt += c;
                ret += cval + c;
            }
            cnt %= 2;
            if (cnt == 0) {
                cnt += 2;
            }
            if (cnt == 1 and v == nonLeafV) {
                ret = -1;
            }
            return {ret, cnt};
        };
        std::cout << dfs(dfs, nonLeafV, -1).first << std::endl;
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30