Submission #702344

#	Time	Username	Problem	Language	Result	Execution time	Memory
702344		Cyanmond	Spring cleaning (CEOI20_cleaning)	C++17	28 / 100	1085 ms	14608 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());
    const int countBaseLeaf = std::count(degree.begin(), degree.end(), 1);
    std::vector<bool> isEven(N);
    std::vector<int> parent(N);
    auto dfs = [&](auto &&self, const int v, const int p) -> bool {
        parent[v] = p;

        bool res = false;
        if (baseTree[v].size() == 1) {
            res = true;
        }
        for (const int t : baseTree[v]) {
            if (t == p) {
                continue;
            }
            res ^= self(self, t, v);
        }
        isEven[v] = not res;
        return res;
    };
    dfs(dfs, nonLeafV, -1);
    int baseAnswer = N - 1 + std::count(isEven.begin(), isEven.end(), true);

    for (int q = 0; q < Q; ++q) {
        int countLeaf = countBaseLeaf;
        int answer = baseAnswer;
        auto toup = [&](auto &&self, const int v) -> void {
            answer -= isEven[v];
            isEven[v] = not isEven[v];
            answer += isEven[v];
            if (parent[v] != -1) self(self, parent[v]);
        };

        for (int i = 0; i < D[q]; ++i) {
            const int v = L[q][i];
            if (degree[v] != 1) {
                ++countLeaf;
                ++answer;
                toup(toup, v);
            } else {
                ++answer;
            }
            ++degree[v];
        }
        if (countLeaf % 2 == 1) {
            answer = -1;
        }
        std::cout << answer - isEven[nonLeafV] << std::endl;

        for (int i = 0; i < D[q]; ++i) {
            const int v = L[q][i];
            --degree[v];
            if (degree[v] != 1) {
                toup(toup, v);
            }
        }
    }
}

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