Submission #1234978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234978		t_holl	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1095 ms	11844 KiB

cleaning

#include <bits/stdc++.h>
#define int long long

#define MULTITEST false

using namespace std;

const int INF = 1e18;

vector<int> vp;
vector<vector<int>> roads;

int res = 0;

int compute (int node, int parent) {
    int cnt = 0;
    for (int next : roads[node]) if (next != parent)
        cnt += compute(next, node);
    cnt += vp[node];
    vp[node] = 0;
    if (cnt == 0) cnt ++;

    if ((cnt & 1) == 0) res ++;
    res ++;

    return cnt;
}

void solve () {
    int N, Q; cin >> N >> Q;

    vp.resize(N);
    roads.resize(N);

    vector<int> deg(N);

    for (int i = 1; i < N; i ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        roads[a].push_back(b);
        roads[b].push_back(a);
        deg[a] ++; deg[b] ++;
    }

    int root = 0;
    for (; root < N; root ++)
        if (deg[root] != 1)
            break ;
    
    for (int i = 0; i < Q; i ++) {
        int d;
        cin >> d;

        for (int j = 0; j < d; j ++) {
            int x;
            cin >> x;
            x --;

            vp[x] ++;
        }

        res = 0;
        int nl = compute(root, -1);

        if ((nl) & 1) cout << -1 << "\n";
        else cout << (d + res - 2) << "\n";
    }
}

signed main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T = 1;
    if (MULTITEST) cin >> T;

    for (int t = 0; t < T; t ++) solve();
}

• 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