Submission #1226960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226960		Warinchai	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	123 ms	18244 KiB

cleaning

#include<bits/stdc++.h>
using namespace std;
vector<int>adj[100005];
int sz[100005],hv[100005],hd[100005],pa[100005],in[100005],out[100005];
int cur=0;
int val[100005];
int n,q;
int cnt=0;
int rt=0;
int isl[100005];

struct segtree{
    int info[400005];
    int lz[400006];
    void push(int st,int en,int i){
        if(lz[i]==0)return;
        info[i]=(en-st+1-info[i]);
        if(st!=en)lz[i*2]^=lz[i],lz[i*2+1]^=lz[i];
        lz[i]=0;
    }
    void inv(int st,int en,int i,int l,int r){
        push(st,en,i);
        if(st>r||en<l)return;
        if(st>=l&&en<=r)return lz[i]=1,push(st,en,i);
        int m=(st+en)/2;
        inv(st,m,i*2,l,r);
        inv(m+1,en,i*2+1,l,r);
        info[i]=info[i*2]+info[i*2+1];
    }
    void build(int st,int en,int i){
        if(st==en){
            return void(info[i]=val[st]);
        }
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
        //cerr<<"info:"<<i<<" "<<info[i*2]<<"+"<<info[i*2+1]<<"\n";
    }
}tr;

void dfssz(int u,int p){
    sz[u]=1;
    for(auto x:adj[u]){
        if(x==p)continue;
        dfssz(x,u);
        sz[u]+=sz[x];
        if(sz[hv[u]]<sz[x])hv[u]=x;
    }
}

void dfs(int u,int p,int h){
    in[u]=++cur;
    //cerr<<"in:"<<u<<" "<<in[u]<<"\n";
    hd[u]=h;
    pa[u]=p;
    if(hv[u])dfs(hv[u],u,h);
    for(auto x:adj[u])if(x!=p&&x!=hv[u]){
        dfs(x,u,x);
    }
    out[u]=cur;
}

void init(int u,int p){
    int ch=0;
    for(auto x:adj[u])if(x!=p){
        init(x,u);
        val[in[u]]^=val[in[x]];
        ch++;
    }
    if(ch==0){
        val[in[u]]=1;
        cnt++;
        isl[u]=1;
        //cerr<<"ch:"<<u<<"\n";
    }
    //cerr<<"val:"<<u<<" "<<val[in[u]]<<"\n";
}

void rv(int x){
    int temp=x;
    //cerr<<"Rv:"<<temp<<"\n";
    while(temp){
        int h=hd[temp];
        tr.inv(1,n,1,in[h],in[temp]);
        //cerr<<in[h]<<" "<<in[temp]<<"\n";
        temp=pa[h];
    }
}

int vis[100005];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++)if(adj[i].size()!=1){
        rt=i;
        break;
    }
    //cerr<<"rt:"<<rt<<"\n";
    dfssz(rt,0);
    dfs(rt,0,rt);
    init(rt,0);
    tr.build(1,n,1);
    //cerr<<"work\n";
    //cerr<<cnt<<"\n";
    //cerr<<tr.info[1]<<"\n";
    for(int i=0;i<q;i++){
        int d;cin>>d;
        vector<int>v;
        vector<int>lf;
        int temp=cnt;
        for(int j=0;j<d;j++){
            int x;cin>>x;
            temp++;
            if(isl[x]&&vis[x]==0)temp--,lf.push_back(x),vis[x]=1;
            else{
                v.push_back(x);
                rv(x);
                //cerr<<"rv:"<<x<<"\n";
            }
        }
        //cerr<<"Q:"<<temp<<"\n";
        if(temp%2==0)cout<<(2*(n-1)-tr.info[1]+d)<<"\n";
        else cout<<"-1\n";
        for(auto x:lf)vis[x]=0;
        for(auto x:v)rv(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