Submission #1159337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159337		adiyer	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1098 ms	26696 KiB

cleaning

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;

const int MAXN = 200005;

int n, q, ans, sz;
int u[MAXN], v[MAXN], dp[MAXN];

vector < int > g[MAXN], adj[MAXN];

void dfs(int v, int p){
    if(g[v].size() == 1) dp[v] = 1;
    else dp[v] = 0;
    for(int u : g[v]){
        if(u == p) continue;
        dfs(u, v);
    }
    for(int u : g[v]){
        if(u == p) continue;
        dp[v] += dp[u];
    }
    if(v == 1) dp[v] = 0;
    while(dp[v] > 2) dp[v] -= 2;
    ans += dp[v];
    // cout << "vertex: " << v << " dp: " << dp[v] << '\n';
}

signed main(){
    cin >> n >> q, sz = n;
    for(int i = 1; i < n; i++) cin >> u[i] >> v[i], adj[u[i]].pb(v[i]), adj[v[i]].pb(u[i]);
    while(q--){
        for(int i = 1; i <= sz; i++) g[i].clear();
        for(int i = 1; i <= n; i++) g[i] = adj[i];
        int d, x, cnt = 0; cin >> d, sz = n, ans = 0;
        while(d--) cin >> x, sz++, g[x].pb(sz), g[sz].pb(x);
        for(int i = 1; i <= sz; i++)
            if(g[i].size() == 1)
                cnt++;
        if(cnt % 2){
            cout << "-1\n"; 
            continue;
        }
        ans = 0, dfs(1, 1);
        cout << ans << '\n';
    }
}

/* 
g++ cleaning.cpp -o program.exe
program.exe
7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1

*/

• 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