Submission #1282929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282929		HiepVu217	Spring cleaning (CEOI20_cleaning)	C++20	28 / 100	140 ms	19296 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,q;
vector<int> dsk[N];
int leaves[N];
int sz[N], parv[N], depthv[N];
int chainh[N], chainid[N], pos[N], ar[N];
int curpos=1, curchain=1;
int st[4*N], lazy[4*N];
int R;

void dfs_leaves(int u,int p,int root){
    if(dsk[u].size()==1 && u!=root) leaves[u]=1; else leaves[u]=0;
    for(int v:dsk[u]) if(v!=p){
        dfs_leaves(v,u,root);
        leaves[u]+=leaves[v];
    }
}

void dfs_sz(int u,int p){
    sz[u]=1;
    for(int v:dsk[u]) if(v!=p){
        parv[v]=u;
        depthv[v]=depthv[u]+1;
        dfs_sz(v,u);
        sz[u]+=sz[v];
    }
}

void hld(int u,int p){
    if(!chainh[curchain]) chainh[curchain]=u;
    chainid[u]=curchain;
    pos[u]=curpos;
    ar[curpos]=u;
    curpos++;
    int heavy=0;
    for(int v:dsk[u]) if(v!=p){
        if(heavy==0 || sz[v]>sz[heavy]) heavy=v;
    }
    if(heavy) hld(heavy,u);
    for(int v:dsk[u]) if(v!=p && v!=heavy){
        curchain++;
        hld(v,u);
    }
}

void build(int id,int l,int r){
    if(l==r){
        st[id] = (leaves[ar[l]] % 2 == 0);
        return;
    }
    int mid = (l + r) >> 1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    st[id] = st[id<<1] + st[id<<1|1];
}

void down(int id,int l,int r){
    if(!lazy[id]) return;
    int mid = (l + r) >> 1;
    int left = id<<1, right = id<<1|1;
    st[left] = (mid - l + 1) - st[left];
    lazy[left] ^= 1;
    st[right] = (r - mid) - st[right];
    lazy[right] ^= 1;
    lazy[id]=0;
}

void update_seg(int id,int l,int r,int x,int y){
    if(l>y || x>r) return;
    if(x<=l && r<=y){
        st[id] = (r - l + 1) - st[id];
        lazy[id] ^= 1;
        return;
    }
    int mid = (l + r) >> 1;
    down(id,l,r);
    update_seg(id<<1,l,mid,x,y);
    update_seg(id<<1|1,mid+1,r,x,y);
    st[id] = st[id<<1] + st[id<<1|1];
}

int get_seg(int id,int l,int r,int x,int y){
    if(l>y || x>r) return 0;
    if(x<=l && r<=y) return st[id];
    int mid = (l + r) >> 1;
    down(id,l,r);
    return get_seg(id<<1,l,mid,x,y) + get_seg(id<<1|1,mid+1,r,x,y);
}

int lca(int u,int v){
    while(chainid[u] != chainid[v]){
        if(chainid[u] > chainid[v]) u = parv[chainh[chainid[u]]];
        else v = parv[chainh[chainid[v]]];
    }
    if(depthv[u] < depthv[v]) return u;
    return v;
}

void updatePath(int u,int v){
    int L = lca(u,v);
    while(chainid[u] != chainid[L]){
        update_seg(1,1,R,pos[chainh[chainid[u]]], pos[u]);
        u = parv[chainh[chainid[u]]];
    }
    while(chainid[v] != chainid[L]){
        update_seg(1,1,R,pos[chainh[chainid[v]]], pos[v]);
        v = parv[chainh[chainid[v]]];
    }
    if(depthv[u] < depthv[v]){
        update_seg(1,1,R,pos[u]+1,pos[v]);
    } else {
        update_seg(1,1,R,pos[v]+1,pos[u]);
    }
}

int deg[N], cnt[N];
bool isLeaf[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<n;i++){int u,v;cin>>u>>v;dsk[u].push_back(v);dsk[v].push_back(u);}
    int root=1;
    for(int i=1;i<=n;i++) if(dsk[i].size()>1) {root=i;break;}
    dfs_leaves(root,0,root);
    depthv[root]=0; parv[root]=0;
    dfs_sz(root,0);
    hld(root,0);
    R = curpos - 1;
    build(1,1,R);
    int cntLeaves=0;
    for(int i=1;i<=n;i++){ deg[i]=dsk[i].size(); if(deg[i]<=1){ cntLeaves++; isLeaf[i]=true;} else isLeaf[i]=false; }
    while(q--){
        int z;cin>>z; vector<int> a(z);
        for(int i=0;i<z;i++) cin>>a[i];
        int curLeaves = cntLeaves;
        vector<int> s;
        for(int i=0;i<z;i++){
            s.push_back(a[i]);
            if(deg[a[i]]<=1) curLeaves--;
            curLeaves++;
            cnt[a[i]]++;
            deg[a[i]]++;
        }
        sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end());
        if(curLeaves & 1){
            cout<<-1<<"\n";
            for(auto x:s){ deg[x]=dsk[x].size(); cnt[x]=0; }
            continue;
        }
        for(auto x:s){
            if(isLeaf[x] && ((cnt[x] & 1) == 0)) updatePath(1,x);
            else if(!isLeaf[x] && ((cnt[x] & 1) == 1)) updatePath(1,x);
        }
        cout<<n + z - 2 + st[1]<<"\n";
        for(auto x:s){
            if(isLeaf[x] && ((cnt[x] & 1) == 0)) updatePath(1,x);
            else if(!isLeaf[x] && ((cnt[x] & 1) == 1)) updatePath(1,x);
        }
        for(auto x:s){ deg[x]=dsk[x].size(); cnt[x]=0; }
    }
    return 0;
}

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