Submission #1186135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186135		Unforgettablepl	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	200 ms	44608 KiB

cleaning

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

#define int long long

const int modulo = 1e9+7;

struct segtree{
    vector<int> tree,lazy;
    int N;
    segtree(int N):tree(8*N),lazy(9*N),N(N){}
    int sum(int L,int R,int x,int QL,int QR){
        int mid = (L+R)/2;
        if(lazy[x]){
            lazy[x]=0;
            tree[x] = R-L+1-tree[x];
            lazy[2*x]^=1;
            lazy[2*x+1]^=1;
        }
        if(QL<=L and R<=QR)return tree[x];
        if(R<QL or QR<L)return 0;
        return sum(L,mid,2*x,QL,QR)+sum(mid+1,R,2*x+1,QL,QR);
    }
    int sum(int x){
        return sum(1,N,1,1,x);
    }
    void flipUpdate(int L,int R,int x,int QL,int QR){
        int mid = (L+R)/2;
        if(lazy[x]){
            lazy[x]=0;
            tree[x] = R-L+1-tree[x];
            lazy[2*x]^=1;
            lazy[2*x+1]^=1;
        }
        if(R<QL or QR<L)return;
        if(QL<=L and R<=QR){
            tree[x] = R-L+1-tree[x];
            lazy[2*x]^=1;
            lazy[2*x+1]^=1;
            return;
        }
        flipUpdate(L,mid,2*x,QL,QR);
        flipUpdate(mid+1,R,2*x+1,QL,QR);
        tree[x]=tree[2*x]+tree[2*x+1];
    }
    void flipUpdate(int L,int R){
        flipUpdate(1,N,1,L,R);
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,Q;
    cin >> N >> Q;
    vector<vector<int>> adj(N+1);
    vector<vector<int>> newAdj(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;
    segtree bit(N);
    {
        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++;newAdj[x].emplace_back(i);}
            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;
        }
    }
    swap(adj,newAdj);
    {
        vector<int> subsize(N+1);
        function<int(int)> dfs = [&](int x){
            subsize[x]=1;
            for(int&i:adj[x]){
                auto t = dfs(i);
                subsize[x]+=t;
                if(t>subsize[adj[x][0]])swap(adj[x][0],i);
            }
            return subsize[x];
        };
        assert(dfs(root)==N);
    }
    vector<int> head(N+1);
    vector<int> idx(N+1);
    {
        int c = 0;
        function<void(int)> dfs = [&](int x){
            idx[x]=++c;
            if(status[x])bit.flipUpdate(idx[x],idx[x]);
            for(int&i:adj[x]){
                if(i==adj[x][0])head[i]=head[x];
                else head[i]=i;
                dfs(i);
            }
        };
        head[root]=root;
        dfs(root);
    }
    auto flip = [&](int x){
        while(x){
            int a = idx[head[x]];
            int b = idx[x];
            bit.flipUpdate(a,b);
            x = par[head[x]];
        }
        status[root] = bit.sum(1);
        cntEven = N-bit.sum(N);
    };
    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: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30