Submission #1159388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159388		adiyer	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	1095 ms	327680 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], par[MAXN], dp2[MAXN];

vector < int > g[MAXN], vec;

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

void up(ll v){
    if(v == 1) return;
    ans -= dp[v];
    dp[v]++;
    if(dp[v] > 2) dp[v] -= 2;
    vec.pb(v);
    ans += dp[v];
    up(par[v]);
}

signed main(){
    int d, x, cnt, pcnt = 0, cur;
    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);
    dfs(1, 1), cur = ans;
    while(q--){
        vec.clear();
        cnt = pcnt, ans = cur, 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);
            par[sz] = x, up(sz);
        }
        for(auto it : vec) dp[it] = dp2[it];
        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; 
        }
        
        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: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30