Submission #1282894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282894		goldencheems	Spring cleaning (CEOI20_cleaning)	C++20	17 / 100	201 ms	15296 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pu push_back
typedef pair <long,long> ii;
const int N=1e6;
long long mod=1e9;
int n;
int a[N+1],d[N+1],sz[N+1],pa[N+1],head[N+1],pos[N+1],arr[N+1],curchain=1,chainid[N+1],curpos=1,ss[N+10],ans,lazy[N*4+10],root,res,lnum;
vector <int> adj[N+1];
bool leaf[N+10],o[N+10];
struct Node{
    int c1,c2;
    Node operator + (const Node &o) const{
            return {c1+o.c1,c2+o.c2};
        }
    };
Node node[4*N+1];

void dfs(int u,int p){
    sz[u]=1;
    if(adj[u].size()==1 and p){
        ss[u]=1;
        leaf[u]=true;
        o[u]=true;
        lnum++;
    }
    for(auto v:adj[u]){
        if(v==p) continue;
        pa[v]=u;
        d[v]=d[u]+1;
        dfs(v,u);
        sz[u]+=sz[v];
        ss[u]+=ss[v];
    }
    }
void hld(int u,int p){
    if(head[curchain]==0) head[curchain]=u;
    chainid[u]=curchain;
    pos[u]=curpos;
    arr[curpos]=u;
    curpos++;
    int nxt=0;
    for(auto v:adj[u]){
        if(v==p) continue;
        if(nxt==0 || sz[v]>sz[nxt]) nxt=v;
    }
    if(nxt)
    hld(nxt,u);
    for(auto v:adj[u]){
        if(v!=p && v!=nxt){
            curchain++;
            hld(v,u);
        }
    }
    }
int lca(int u,int v){
    while(chainid[u]!=chainid[v]){
        if(chainid[u]>chainid[v])
            u=pa[head[chainid[u]]];
        else
            v=pa[head[chainid[v]]];
    }
    if(d[u]>d[v]) return v;
    else return u;
    }
void add(int id,int w){
    if(w%2==1){
        ans-=node[id].c1+node[id].c2*2;
        swap(node[id].c1,node[id].c2);
        ans+=node[id].c1+node[id].c2*2;
        lazy[id]+=w;
    }
}
void down(int id){
    int t=lazy[id];
    add(id*2,t);
    add(id*2+1,t);
    lazy[id]=0;
    }
void Build(int id,int l,int r){
    if(l==r){
        if(arr[l]==root) return;
        node[id].c1=(ss[arr[l]]%2==1);
        node[id].c2=(ss[arr[l]]%2==0);
        res+=node[id].c1+node[id].c2*2;
        return;
    }
    int mid=(l+r)/2;
    Build(id*2,l,mid);
    Build(id*2+1,mid+1,r);
    node[id]=node[id*2]+node[id*2+1];
}
void Update(int id,int l,int r,int u,int v){
    if(l>v or r<u) return;
    if(l>=u and r<=v){

        add(id,1);
        return;
    }
    down(id);
    int mid=(l+r)/2;
    Update(id*2,l,mid,u,v);
    Update(id*2+1,mid+1,r,u,v);
    node[id]=node[id*2]+node[id*2+1];
    }
void Upd(int u,int v){
    int x=lca(u,v);
    while(chainid[u]!=chainid[x]){
        Update(1,1,n,pos[head[chainid[u]]],pos[u]);
        u=pa[head[chainid[u]]];
    }
    while(chainid[v]!=chainid[x]){
        Update(1,1,n,pos[head[chainid[v]]],pos[v]);
        v=pa[head[chainid[v]]];
    }
    if(d[u]>d[v]){
        Update(1,1,n,pos[v],pos[u]);
    }
    else
        Update(1,1,n,pos[u],pos[v]);

    }

void tinh(){
    int q;
    cin>>n;
    cin>>q;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].pu(v);
        adj[v].pu(u);
    }
    root=1;
    for(int i=1;i<=n;i++){
        if(adj[i].size()>1){
            root=i;
            break;
        }
    }
    dfs(root,0);
    hld(root,0);
    Build(1,1,n);
    //cout<<res<<" "<<root<<'\n';
    while(q--){
        ans=res;
        int k;
        cin>>k;
        int l2=lnum;
        vector <int> z;
        for(int i=1;i<=k;i++){
            cin>>a[i];
            ans++;
            //out<<ans<<" "<<a[i]<<'\n';
            if(a[i]==root) {
                l2++;
                continue    ;
            }

            if(o[a[i]]){
                o[a[i]]=false;
            }
            else{
                l2++;
                Upd(root,a[i]);
                z.pu(a[i]);
            }
            //cout<<ans<<" ";
        }
        if(l2%2==1){
            cout<<-1<<'\n';
            for(int x:z) Upd(root,x);
            continue;
        }
        cout<<ans<<'\n';
        for(int i=1;i<=k;i++){
            if(leaf[a[i]]) o[a[i]]=true;
        }
        for(int x:z) Upd(root,x);
    }

    }
int main(){
    //freopen("jday.inp","r",stdin);
    //freopen("jday.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    tinh();
    return 0;

}
//code của anh Nam đẹp trai nhất CHL

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