Submission #985334

#	Time	Username	Problem	Language	Result	Execution time	Memory
985334		alexdd	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	205 ms	20304 KiB

cleaning

#include<bits/stdc++.h>
using namespace std;
/*ifstream fin("input.in");
ofstream fout("output.out");
#define cin fin
#define cout fout*/
int n,q,root;
vector<int> con[100005];

struct node
{
    int cnt0,cnt1;
    int lazy;
};
node aint[270000];
void propagate(int nod)
{
    if(aint[nod].lazy%2==0)
        return;
    aint[nod*2].lazy++;
    aint[nod*2+1].lazy++;
    swap(aint[nod*2].cnt0, aint[nod*2].cnt1);
    swap(aint[nod*2+1].cnt0, aint[nod*2+1].cnt1);
    aint[nod].lazy=0;
}
void upd(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        aint[nod].lazy++;
        swap(aint[nod].cnt0, aint[nod].cnt1);
        return;
    }
    propagate(nod);
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri));
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri);
    aint[nod].cnt0 = aint[nod*2].cnt0 + aint[nod*2+1].cnt0;
    aint[nod].cnt1 = aint[nod*2].cnt1 + aint[nod*2+1].cnt1;
}

int siz[100005];
int cntf[100005];
int head[100005];
int parent[100005];
int depth[100005];
int pos[100005],curpos;

void dfs(int nod)
{
    siz[nod]=1;
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod])
        {
            parent[adj]=nod;
            depth[adj]=depth[nod]+1;
            dfs(adj);
            cntf[nod] += cntf[adj];
            siz[nod] += siz[adj];
        }
    }
    if(cntf[nod]==0) cntf[nod]=1;
}
void decompose(int nod, int chead)
{
    pos[nod]=++curpos;
    head[nod]=chead;
    int heavy=-1,maxc=-1;
    for(auto adj:con[nod])
        if(adj!=parent[nod] && siz[adj]>maxc)
            maxc=siz[adj], heavy=adj;
    if(heavy!=-1)
        decompose(heavy,chead);
    for(auto adj:con[nod])
        if(adj!=parent[nod] && adj!=heavy)
            decompose(adj,adj);
}
void hld_upd(int a)
{
    for(;head[a]!=root;a=parent[head[a]])
    {
        upd(1,1,n,pos[head[a]],pos[a]);
    }
    upd(1,1,n,pos[root],pos[a]);
}
int aux[100005];
int visited[100005];
bool schimba[100005];
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod].cnt0=1;
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod].cnt0 = aint[nod*2].cnt0 + aint[nod*2+1].cnt0;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    int u,v;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        con[u].push_back(v);
        con[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        if((int)con[i].size()>1)
        {
            root=i;
            break;
        }
    }
    dfs(root);
    decompose(root,root);
    build(1,1,n);
    for(int i=1;i<=n;i++)
        if(cntf[i]%2==1)
            upd(1,1,n,pos[i],pos[i]);
    for(int pas=1;pas<=q;pas++)
    {
        int nr,auxf=0;
        cin>>nr;
        for(int i=1;i<=nr;i++)
        {
            cin>>aux[i];
            if(siz[aux[i]]==1 && visited[aux[i]]!=pas)
            {
                visited[aux[i]]=pas;
                schimba[i]=0;
            }
            else
            {
                auxf++;
                schimba[i]=1;
            hld_upd(aux[i]);
            }
        }
        if((cntf[root]+auxf)%2==1) cout<<-1<<"\n";
        else cout<<aint[1].cnt0*2 + aint[1].cnt1 - 2 + nr<<"\n";
        for(int i=1;i<=nr;i++)
            if(schimba[i])
                hld_upd(aux[i]);
    }
    return 0;
}

• 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