Submission #1167002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167002		lampooppp	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	139 ms	19268 KiB

cleaning

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

const int N=1e5;
vector<int> adj[N+1];
int la[N+1], cl[N+1];
int vis[N+1],chi[N+1];
int pa[N+1],n,m,id[N+1];

struct seg
{
    int odd=0,even=0,lazy=0;
}st[4*N+1];

void dfs(int u)
{
    chi[u]=1;
    cl[u]=0;
    vis[u]=1;
    for(int v : adj[u])
    {
        if(vis[v]) continue;
        pa[v]=u;
        dfs(v);
        chi[u]+=chi[v];
        cl[u]+=cl[v];
        cl[u]%=2;
    }
    if(adj[u].size()==1)
        cl[u]=1;
    //cout << u << " "
}

int chead[N+1], cid[N+1], pos[N+1], ch=1, tme=0;

void hld(int u)
{
    cid[u]=ch;
    pos[u]=++tme;
    id[tme]=cl[u];
    int mx=0;
    int k;
    for(int v : adj[u])
    {
        if(v==pa[u]) continue;
        if(mx<chi[v])
        {
            mx=chi[v];
            k=v;
        }
    }
    if(mx==0) return;
    hld(k);
    for(int v : adj[u])
    {
        if(v==k || v==pa[u]) continue;
        ch++;
        chead[ch]=v;
        hld(v);
    }
}

void push(int x)
{
    if(st[x].lazy==0) return;
    st[x].lazy=0;
    st[x*2].lazy^=1;
    st[x*2+1].lazy^=1;
    swap(st[x*2].odd, st[x*2].even);
    swap(st[x*2+1].odd, st[x*2+1].even);
}

void update(int x, int low, int hi, int i, int j)
{
    if(low> hi || low > j || hi<i) return;
    if(low>=i && hi<=j)
    {
        st[x].lazy^=1;
        swap(st[x].odd, st[x].even);
        return;
    }
    push(x);
    int mid=low+hi>>1;
    update(x*2,low,mid,i,j);
    update(x*2+1,mid+1,hi,i,j);
    st[x].odd=st[x*2].odd+st[x*2+1].odd;
    st[x].even=st[x*2].even+st[x*2+1].even;
}

int get(int x, int low, int hi, int i)
{
    if(low==hi) return st[x].odd;
    int mid=low+hi>>1;
    push(x);
    if(i<=mid) return get(x*2,low,mid,i);
    return get(x*2+1,mid+1,hi,i);
}

void updatetree(int u, int v)
{
    while(cid[u]!=cid[v])
    {
        update(1,1,n,pos[chead[cid[v]]],pos[v]);
        v=pa[chead[cid[v]]];
    }
    update(1,1,n,pos[u],pos[v]);
}

void build(int x, int low, int hi)
{
    if(low==hi)
    {
        if(id[low])
        {
            st[x].odd=1;
        }
        else st[x].even=1;
        return;
    }
    int mid=low+hi>>1;
    build(x*2,low,mid);
    build(x*2+1,mid+1,hi);
    st[x].odd=st[x*2].odd+st[x*2+1].odd;
    st[x].even=st[x*2].even+st[x*2+1].even;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<n;++i)
    {
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int base;
    for(int i=1;i<=n;++i)
    {
        if(adj[i].size()==1)
        {
            la[i]=1;
        }
        else
        {
            base=i;
        }
    }
    dfs(base);
    chead[1]=base;
    hld(base);
    build(1,1,n);
//    for(int i=1;i<=n;++i) cout << cl[i] << " ";
//    cout << '\n';
    //cout << st[1].even<<"\n";
    while(m--)
    {
        int k;
        cin >> k;
        vector<int> p;
        for(int i=1;i<=k;++i)
        {
            int u;
            cin >> u;
            p.push_back(u);
            if(la[u]==1)
            {
                la[u]=2;
            }
            else
            {
                updatetree(base,u);
            }
        }
        if(get(1,1,n,pos[base]))
        {
            cout << -1 << '\n';
        }
        else
        {
            int cnt = st[1].even-1;
            //cout << cnt << " ";
            cout << n-1+cnt+k << '\n';
        }
        for(int u : p)
        {
            if(la[u]==2)
            {
                la[u]=1;
            }
            else
            {
                updatetree(base,u);
            }
        }
    }
}

• 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