Submission #1186108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186108		Unforgettablepl	Spring cleaning (CEOI20_cleaning)	C++20	28 / 100	1096 ms	12572 KiB

cleaning

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

#define int long long

const int modulo = 1e9+7;


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,Q;
    cin >> N >> Q;
    vector<vector<int>> adj(N+1);
    for(int i=1;i<N;i++){
        int u,v;cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    vector<int> par(N+1);
    vector<int> status(N+1);
    vector<bool> isLeaf(N+1);
    int cntEven = 0;
    int root = 0;
    {
        function<int(int,int)> dfs = [&](int x,int p){
            int curr = 0;
            int children = 0;
            par[x]=p;
            for(int&i:adj[x])if(i!=p){curr^=dfs(i,x);children++;}
            if(children==0){curr=1;isLeaf[x]=true;}
            if(curr==0)cntEven++;
            status[x]=curr;
            return curr;
        };
        for(int i=1;i<=N;i++)if(adj[i].size()>1){
            dfs(i,0);
            root = i;
            break;
        }
    }
    auto flip = [&](int x){
        while(x){
            status[x]^=1;
            if(status[x])cntEven--;
            else cntEven++;
            x = par[x];
        }
    };
    vector<bool> isModified(N+1);
    for(int i=1;i<=Q;i++){
        int D;cin>>D;
        vector<int> updates(D);
        for(int&x:updates){
            cin >> x;
            if(isLeaf[x] and !isModified[x])isModified[x]=true;
            else flip(x);
        }
        if(status[root]==0)cout << cntEven+N+D-2 << '\n';
        else cout << "-1\n";
        for(int&x:updates){
            if(isLeaf[x] and isModified[x])isModified[x]=false;
            else flip(x);
        }
    }
}

• 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