oj.uz

Submission #702333

# Submission time Handle Problem Language Result Execution time Memory
702333 2023-02-23T15:08:40 Z Cyanmond Spring cleaning (CEOI20_cleaning) C++17
34 / 100
 1000 ms 20732 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1088 ms 4252 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5880 KB Output is correct
2 Correct 28 ms 5772 KB Output is correct
3 Correct 68 ms 15520 KB Output is correct
4 Correct 93 ms 16736 KB Output is correct
5 Correct 117 ms 18540 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7628 KB Output is correct
2 Correct 32 ms 7600 KB Output is correct
3 Correct 86 ms 16184 KB Output is correct
4 Correct 111 ms 19980 KB Output is correct
5 Correct 70 ms 14584 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 3932 KB Output is correct
2 Correct 339 ms 3432 KB Output is correct
3 Correct 477 ms 3236 KB Output is correct
4 Correct 507 ms 3472 KB Output is correct
5 Correct 470 ms 3484 KB Output is correct
6 Correct 547 ms 3724 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 13568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 20732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1088 ms 4252 KB Time limit exceeded
3 Halted 0 ms 0 KB -