Submission #1209341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209341		irmuun	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	1094 ms	11872 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=2e5+5;

ll n,q,sub[N],par[N],even=0;
vector<ll>g[N];

void recalc(ll x){
    if(sub[x]%2==0) even--;
    sub[x]=(g[x].size()==1&&x==1?1:0);
    for(ll y:g[x]){
        if(y!=par[x]){
            sub[x]+=sub[y];
        }
    }
    if(sub[x]%2==0) even++;
}

void find_par(ll x,ll p){
    par[x]=p;
    for(ll y:g[x]){
        if(y!=p){
            find_par(y,x);
        }
    }
}

void dfs(ll x,ll p){
    sub[x]=0;
    if(g[x].size()==1) sub[x]=1;
    for(ll y:g[x]){
        if(y!=p){
            dfs(y,x);
            sub[x]+=sub[y];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for(ll i=1;i<n;i++){
        ll u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    find_par(1,1);
    dfs(1,1);
    for(ll i=2;i<=n;i++){
        if(sub[i]%2==0){
            even++;
        }
    }
    while(q--){
        ll d;
        cin>>d;
        vector<ll>a(d);
        for(ll i=0;i<d;i++){
            cin>>a[i];
            g[a[i]].pb(n+i+1);
            g[n+i+1].pb(a[i]);
            sub[n+i+1]++;
            ll x=a[i];
            do{
                recalc(x);
                x=par[x];
            }while(x!=1);
        }
        if(sub[1]&1){
            cout<<-1<<"\n";
        }
        else{
            cout<<even+n+d-1<<"\n";
        }
        for(ll i=d-1;i>=0;i--){
            g[a[i]].pop_back();
            g[n+i+1].pop_back();
            sub[n+i+1]=0;
            ll x=a[i];
            do{
                recalc(x);
                x=par[x];
            }while(x!=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