Submission #1208917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208917		irmuun	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1096 ms	19592 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];
vector<ll>g[N];

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);
    }
    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]);
        }
        ll root=0;
        for(ll i=1;i<=n+d;i++){
            if(g[i].size()>=2){
                root=i;
                break;
            }
        }
        dfs(root,root);
        if(sub[root]%2==1){
            cout<<-1<<"\n";
        }
        else{
            ll ans=n+d-2;
            for(ll i=1;i<=n+d;i++){
                if(sub[i]%2==0){
                    ans++;
                }
            }
            cout<<ans<<"\n";
        }
        for(ll i=d-1;i>=0;i--){
            g[a[i]].pop_back();
            g[n+i+1].pop_back();
        }
    }
}

• 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