Submission #866034

#	Time	Username	Problem	Language	Result	Execution time	Memory
866034		vnm06	Spring cleaning (CEOI20_cleaning)	C++14	18 / 100	1049 ms	29020 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 otg[300005];
int pref[300005];

int prom[300005], brprom=0;
int smqna[300005];

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)) {otg[pos[i]]=1;}
    }
    for(int i=1; i<=n; i++) pref[i]=otg[i]+pref[i-1];
    for(int i=0; i<q; i++)
    {
        int d, brl=lst[kor], otgov=0;
        brprom=0;
        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];
            while(tekchain!=1)
            {
                int lpos=chain[tekchain][0];
               /// cout<<lpos<<" "<<tpos<<endl;
                prom[brprom]=lpos;
                smqna[lpos]^=1;
                brprom++;
                prom[brprom]=tpos+1;
                smqna[tpos+1]^=1;
                brprom++;
                tv=par[red[lpos]];
                tpos=pos[tv];
                tekchain=to_chain[tv];
            }
            if(tpos>1) 
            {
                prom[brprom]=2;
                smqna[2]^=1;
                brprom++;
                prom[brprom]=tpos+1;
                smqna[tpos+1]^=1;
                brprom++;
            }
        }
            sort(prom, prom+brprom);
            int lpos=1, tsm=0;
            for(int i=0; i<brprom; i++)
            {
                int npos=prom[i];
                if(!smqna[prom[i]]) continue;
                smqna[prom[i]]=0;
                if(!tsm) otgov+=pref[npos-1]-pref[lpos-1];
                else otgov+=(npos-lpos)-(pref[npos-1]-pref[lpos-1]);
                tsm^=1;
                lpos=npos;
            }
            ///cout<<brprom<<" "<<tsm<<" "<<pref[n]<<endl;
            if(lpos<=n && !tsm) otgov+=pref[n]-pref[lpos-1];
            else if(lpos<=n) otgov+=(n-lpos+1)-(pref[n]-pref[lpos-1]);
        if(brl&1) cout<<-1<<endl;
        else cout<<n-1+d+otgov<<endl;
        brprom=0;
    }
    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: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30