Submission #1159360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159360		adiyer	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1096 ms	19648 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];

void dfs(int v, int p){
    dp[v] = (g[v].size() == 1);
    for(int u : g[v]){
        if(u == p) continue;
        dfs(u, v), dp[v] += dp[u];
    }
    if(v == 1) dp[v] = 0;
    while(dp[v] > 2) dp[v] -= 2;
    ans += dp[v];
}

signed main(){
    int d, x, cnt, pcnt = 0;
    vector < int > del;
    cin >> n >> q, sz = n;
    for(int i = 1; i < n; i++) cin >> u[i] >> v[i], g[u[i]].pb(v[i]), g[v[i]].pb(u[i]);
    for(int i = 1; i <= n; i++) pcnt += (g[i].size() == 1);
    while(q--){
        cnt = pcnt, ans = 0, sz = n, del.clear(), cin >> d;
        while(d--){ 
            cin >> x, del.pb(x); 
            sz++, cnt = cnt + 1 - (g[x].size() == 1);
            g[x].pb(sz), g[sz].pb(x);
        }
        if(cnt % 2){ 
            while(!del.empty()) g[del.back()].pop_back(), del.pop_back();
            for(ll i = n + 1; i <= sz; i++) g[i].clear();
            cout << "-1\n"; continue; 
        }
        dfs(1, 1);
        while(!del.empty()) g[del.back()].pop_back(), del.pop_back();
        for(ll i = n + 1; i <= sz; i++) g[i].clear();
        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