Submission #759013

#	Time	Username	Problem	Language	Result	Execution time	Memory
759013		gagik_2007	Spring cleaning (CEOI20_cleaning)	C++17	28 / 100	1095 ms	11256 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

#pragma GCC optimize("O2")

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 7;
ll n, m, k;
ll p[N];
vector<int>g[N];
bool is_leaf[N];
int leaf_cnt[N];

void dfs(int v, int par){
    is_leaf[v]=(g[v].size()==1);
    leaf_cnt[v]=is_leaf[v];
    p[v]=par;
    for(int to:g[v]){
        if(to!=par){
            dfs(to,v);
            leaf_cnt[v]+=leaf_cnt[to];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,1);
    int cc=leaf_cnt[1];
    int ans=0;
    for(int v=2;v<=n;v++){
        if(leaf_cnt[v]%2==0){
            ans+=2;
            // cout<<v<<endl;
        }
        else{
            ans++;
        }
    }
    vector<int>was_leaf;
    vector<int>lconi;
    for(int i=0;i<m;i++){
        // cout<<ans<<endl;
        int d;
        cin>>d;
        for(int j=0;j<d;j++){
            int v;
            cin>>v;
            if(is_leaf[v]){
                was_leaf.push_back(v);
                is_leaf[v]=false;
                ans++;
            }
            else{
                ans++;
                cc++;
                lconi.push_back(v);
                while(v!=1){
                    // cout<<v<<endl;
                    if(leaf_cnt[v]%2==0){
                        ans-=2;
                    }
                    else{
                        ans--;
                    }
                    leaf_cnt[v]++;
                    if(leaf_cnt[v]%2==0){
                        ans+=2;
                    }
                    else{
                        ans++;
                    }
                    v=p[v];
                }
            }
        }
        if(cc%2==0)cout<<ans<<endl;
        else cout<<-1<<endl;
        for(int v:lconi){
            ans--;
            cc--;
            while(v!=1){
                if(leaf_cnt[v]%2==0){
                    ans-=2;
                }
                else{
                    ans--;
                }
                leaf_cnt[v]--;
                if(leaf_cnt[v]%2==0){
                    ans+=2;
                }
                else{
                    ans++;
                }
                v=p[v];
            }
        }
        lconi.clear();
        for(int v:was_leaf){
            is_leaf[v]=true;
            ans--;
        }
        was_leaf.clear();
    }
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 19 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30