Submission #866039

#	Time	Username	Problem	Language	Result	Execution time	Memory
866039		vnm06	Spring cleaning (CEOI20_cleaning)	C++14	37 / 100	196 ms	55536 KiB

cleaning

#include<bits/stdc++.h>
#define endl '\n'
 
using namespace std;
 
int n, q, kor=0, brl=0, ans=0, par[300005];
vector<int> gr[300005];
bool used[300005];
int lst[300005], gol[300005];
 
void dfs(int v)
{
    gol[v]=1;
    used[v]=1;
    int brs=gr[v].size();
    if(brs==1) {brl++; lst[v]=1;}
    for(int i=0; i<brs; i++)
    {
        int nv=gr[v][i];
        if(used[nv]) continue;
        par[nv]=v;
        dfs(nv);
        lst[v]+=lst[nv];
        gol[v]+=gol[nv];
    }
    if(v!=kor && !(lst[v]&1)) ans++;
}
 
int nvt[300005];
 
int brchains=1, tv=0;
int chain[300005][2];
int to_chain[300005];
int red[300005], pos[300005];
int stojnost[300005];
 
 
void create_hld(int v)
{
    tv++;
    red[tv]=v;
    pos[v]=tv;
    to_chain[v]=brchains;
    int brs=gr[v].size();
    if(!brs) return;
    create_hld(gr[v][0]);
    for(int i=1; i<brs; i++)
    {
        chain[brchains][1]=tv;
        chain[brchains+1][0]=tv+1;
        brchains++;
        create_hld(gr[v][i]);
    }
}
 
bool promlst[300005];
bool osob[300005];
 
int tree[2000005];
int lazy[2000005];
 
void push_lazy(int v, int le, int ri)
{
    if(!lazy[v]) return;
    tree[v]=(ri-le+1)-tree[v];
    if(le!=ri) {lazy[2*v]^=1; lazy[2*v+1]^=1;}
    lazy[v]=0;
}
 
void update(int v, int le, int ri, int be, int en)
{
    push_lazy(v, le, ri);
    if(le>en || ri<be) return;
    if(be<=le && ri<=en)
    {
        lazy[v]^=1;
        push_lazy(v, le, ri);
        return;
    }
    int mid=(le+ri)/2;
    update(2*v, le, mid, be, en);
    update(2*v+1, mid+1, ri, be, en);
    tree[v]=tree[2*v]+tree[2*v+1];
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>q;
    for(int i=0; i<n-1; i++)
    {
        int a, b;
        cin>>a>>b;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }
    for(int i=1; i<=n; i++) if(gr[i].size()>1 && !kor) kor=i;
    dfs(kor);
 
    for(int i=1; i<=n; i++)
    {
        int brs=gr[i].size();
        if(i==kor) brs++;
        for(int j=0; j<brs-1; j++)
        {
            int nv=gr[i][j];
            if(par[i]==nv) swap(gr[i][j], gr[i][brs-1]);
            else if(gol[nv]>gol[gr[i][0]]) swap(gr[i][j], gr[i][0]);
        }
        gr[i].resize(brs-1);
    }
    /**
    for(int i=1; i<=n; i++)
    {
        cout<<"Vryh "<<i<<": {";
        for(int j=0; j<gr[i].size(); j++) cout<<gr[i][j]<<" ";
        cout<<"}\n";
    }*/
    chain[1][0]=1;
    create_hld(kor);
    chain[brchains][1]=n;
 
    /**
    for(int i=1; i<=n; i++) cout<<red[i]<<" ";
    cout<<endl<<brchains<<endl;
    for(int i=1; i<=brchains; i++) cout<<chain[i][0]<<" "<<chain[i][1]<<endl;
    for(int i=1; i<=n; i++) cout<<pos[i]<<" ";
    cout<<endl;
    for(int i=1; i<=n; i++) cout<<to_chain[i]<<" ";
    cout<<endl;*/
 
    for(int i=1; i<=n; i++)
    {
        if(i!=kor && !(lst[i]&1)) {update(1, 1, n, pos[i], pos[i]);}
    }
    for(int i=0; i<q; i++)
    {
        int d, brl=lst[kor];
        cin>>d;
        brl+=d;
        for(int i=0; i<d; i++)
        {
            cin>>nvt[i];
            if(nvt[i]==kor) continue;
            if(!promlst[nvt[i]] && !gr[nvt[i]].size())
            {
                brl--;
                promlst[nvt[i]]=1;
                osob[i]=1;
                continue;
            }
            int tekchain=to_chain[nvt[i]], tpos=pos[nvt[i]], tv=nvt[i], brskok=0;
            while(tekchain!=1)
            {
                brskok++;
                if(brskok>200)
                {
                    cout<<n/(max(n, n)-min(n, n))<<endl;
                }
                int lpos=chain[tekchain][0];
               /// cout<<lpos<<" "<<tpos<<endl;
                update(1, 1, n, lpos, tpos);
                tv=par[red[lpos]];
                tpos=pos[tv];
                tekchain=to_chain[tv];
            }
            if(tpos>1) update(1, 1, n, 2, tpos);
        }
        if(brl&1) cout<<-1<<endl;
        else cout<<n-1+d+tree[1]<<endl;
        for(int i=0; i<d; i++)
        {
            promlst[nvt[i]]=0;
            if(nvt[i]==kor || osob[i]) 
            {
                osob[i]=0;
                continue;
            }
            osob[i]=0;
            int tekchain=to_chain[nvt[i]], tpos=pos[nvt[i]], tv=nvt[i];
            while(tekchain!=1)
            {
                int lpos=chain[tekchain][0];
                update(1, 1, n, lpos, tpos);
                tv=par[red[lpos]];
                tpos=pos[tv];
                tekchain=to_chain[tv];
            }
            if(tpos>1) update(1, 1, n, 2, tpos);
        }
    }
    return 0;
}
/*
12 3
1 3
4 1
9 1
8 3
3 7
10 2
11 2
2 6
4 5
4 6
9 12
3 1 4 7
2 5 8
1 12
 
 
7 4
1 2
2 4
4 5
5 6
5 7
3 4
1 7
1 4
2 2 4
1 1
*/

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