Submission #1282931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282931		HiepVu217	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	172 ms	17132 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int n,q,sz[N],parv[N],head[N],pos[N],ar[N],ch[N],zp=0,zch=1;
int d[N],a[N],cntLeaf=0;
bool lz[4*N];
vector<int> adj[N];

struct node{
    int c1,c2;
    node operator+(const node&o)const{return{c1+o.c1,c2+o.c2};}
} st[4*N];

int ans=0;

void dfs(int u,int p){
    sz[u]=1;parv[u]=p;
    a[u]=(d[u]==1);cntLeaf+=(d[u]==1);
    for(int v:adj[u]){
        if(v==p)continue;
        dfs(v,u);
        sz[u]+=sz[v];
        a[u]+=a[v];
    }
    if(u>1) ans+=(a[u]%2?1:2);
}

void hld(int u,int p){
    if(!head[zch]) head[zch]=u;
    ch[u]=zch; pos[u]=++zp; ar[zp]=u;
    int bc=0;
    for(int v:adj[u]) if(v!=p && sz[v]>sz[bc]) bc=v;
    if(bc) hld(bc,u);
    for(int v:adj[u]) if(v!=p && v!=bc){ ++zch; hld(v,u); }
}

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

void down(int id){
    swap(st[id*2].c1,st[id*2].c2);
    lz[id*2]^=lz[id];
    swap(st[id*2+1].c1,st[id*2+1].c2);
    lz[id*2+1]^=lz[id];
    lz[id]=0;
}

void update(int id,int l,int r,int u,int v){
    if(v<l||r<u)return;
    if(u<=l&&r<=v){
        ans-=st[id].c1+st[id].c2*2;
        swap(st[id].c1,st[id].c2);
        ans+=st[id].c1+st[id].c2*2;
        lz[id]^=1;
        return;
    }
    if(lz[id]) down(id);
    int mid=(l+r)>>1;
    update(id*2,l,mid,u,v);
    update(id*2+1,mid+1,r,u,v);
    st[id]=st[id*2]+st[id*2+1];
}

void change(int u,int v){
    while(ch[u]!=ch[v]){
        update(1,1,n,pos[head[ch[u]]],pos[u]);
        u=parv[head[ch[u]]];
    }
    update(1,1,n,pos[v]+1,pos[u]);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>q;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        ++d[u]; ++d[v];
    }

    dfs(1,0);
    hld(1,0);
    build(1,1,n);

    for(int i=1,m;i<=q;i++){
        cin>>m;
        vector<int>b(m);
        for(int j=0;j<m;j++){
            int u;cin>>u;b[j]=u;
            if(d[u]==1)--cntLeaf; else change(u,1);
            ++d[u];++cntLeaf;++ans;
        }
        if(cntLeaf&1) cout<<"-1\n";
        else cout<<ans<<"\n";
        for(int u:b){
            --d[u];--ans;--cntLeaf;
            if(d[u]==1)++cntLeaf; else change(u,1);
        }
    }
}

• 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