Submission #305049

#	Time	Username	Problem	Language	Result	Execution time	Memory
305049		nicolaalexandra	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	623 ms	30192 KiB

cleaning

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

int whatChain[DIM],chainFatherNode[DIM],level[DIM],positionInChain[DIM],Size[DIM];
int frunza[DIM],f[DIM],mrk[DIM],fth[DIM],g[DIM],v[DIM];
vector <int> chains[DIM],L[DIM];
set <int> w;
int nr_chains,n,q,i,j,x,y,m,rad,sol,sum;

struct segment_tree{
    int cnt; /// cate noduri au nr par de frunze in subarborele lor
    int lazy;
};
vector <segment_tree> aint[DIM];

void dfs (int nod, int tata){

    Size[nod] = 1;
    level[nod] = 1 + level[tata];
    fth[nod] = tata;
    int ok = 0;
    for (auto vecin : L[nod])
        if (vecin != tata){
            ok = 1;
            dfs (vecin,nod);
            Size[nod] += Size[vecin];
            f[nod] += f[vecin]; /// cate frunze am in subarborele lui nod
        }

    if (!ok){
        nr_chains++;
        chains[nr_chains].push_back(0);
        chains[nr_chains].push_back(nod);
        positionInChain[nod] = 1;
        whatChain[nod] = nr_chains;
        f[nod] = frunza[nod] = 1;
    } else {
        int maxi = 0, heavy_son = 0;
        for (auto vecin : L[nod]){
            if (vecin == tata)
                continue;
            if (Size[vecin] > maxi)
                maxi = Size[vecin], heavy_son = vecin;
        }

        chains[whatChain[heavy_son]].push_back(nod);
        whatChain[nod] = whatChain[heavy_son];
        positionInChain[nod] = chains[whatChain[heavy_son]].size()-1;

        for (auto vecin : L[nod]){
            if (vecin != tata && vecin != heavy_son)
                chainFatherNode[whatChain[vecin]] = nod;
        }}}


void build (int chain, int nod, int st, int dr){
    if (st == dr){
        if (f[chains[chain][st]] % 2 == 0) /// are nr par de frunze
            aint[chain][nod].cnt = 1;
        return;
    }

    int mid = (st+dr)>>1;
    build (chain,nod<<1,st,mid);
    build (chain,(nod<<1)|1,mid+1,dr);

    aint[chain][nod].cnt = aint[chain][nod<<1].cnt + aint[chain][(nod<<1)|1].cnt;
}

void update_lazy (int chain, int nod, int st, int dr){
    if (!aint[chain][nod].lazy)
        return;
    if (st != dr){
        int fiu_st = nod<<1, fiu_dr = (nod<<1)|1, mid = (st+dr)>>1;
        aint[chain][fiu_st].cnt = mid - st + 1 - aint[chain][fiu_st].cnt;
        aint[chain][fiu_st].lazy = 1 - aint[chain][fiu_st].lazy;

        aint[chain][fiu_dr].cnt = dr - mid - aint[chain][fiu_dr].cnt;
        aint[chain][fiu_dr].lazy = 1 - aint[chain][fiu_dr].lazy;

    }
    aint[chain][nod].lazy = 0;
}

void update (int chain, int nod, int st, int dr, int x, int y){

    update_lazy (chain,nod,st,dr);
    if (x <= st && dr <= y){
        /// trb sa dau reverse
        sol -= aint[chain][nod].cnt;
        aint[chain][nod].cnt = (dr - st + 1) - aint[chain][nod].cnt;
        sol += aint[chain][nod].cnt;

        aint[chain][nod].lazy = 1;

        update_lazy (chain,nod,st,dr);
        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid)
        update (chain,nod<<1,st,mid,x,y);
    if (y > mid)
        update (chain,(nod<<1)|1,mid+1,dr,x,y);

    update_lazy (chain,nod<<1,st,mid);
    update_lazy (chain,(nod<<1)|1,mid+1,dr);

    aint[chain][nod].cnt = aint[chain][nod<<1].cnt + aint[chain][(nod<<1)|1].cnt;
}

void update_heavy (int x, int y){
    if (whatChain[x] == whatChain[y]){
        int posx = positionInChain[x], posy = positionInChain[y];
        if (posx > posy)
            swap (posx,posy);
        update (whatChain[x],1,1,chains[whatChain[x]].size()-1,posx,posy);
        return;
    }

    if (level[chainFatherNode[whatChain[x]]] <= level[chainFatherNode[whatChain[y]]])
        swap (x,y);

    update (whatChain[x],1,1,chains[whatChain[x]].size()-1,positionInChain[x],chains[whatChain[x]].size()-1);

    int nr = chainFatherNode[whatChain[x]];
    update_heavy (nr,y);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>q;
    for (i=1;i<n;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
        g[x]++, g[y]++;
    }

    for (i=1;i<=n;i++)
        if (g[i] > 1){
            rad = i;
            break;
        }

    dfs (rad,0);

    for (i=1;i<=nr_chains;i++){
        aint[i].resize(chains[i].size()*4);
        build (i,1,1,chains[i].size()-1);
        sum += aint[i][1].cnt;
    }

    for (;q--;){
        cin>>m;

        /// calculez nr de frunze
        int nr = f[rad] + m;

        w.clear();
        for (i=1;i<=m;i++){
            cin>>v[i];
            if (frunza[v[i]] && !mrk[v[i]]) /// asta nu o sa mai fie frunza
                nr--;
            mrk[v[i]]++;
            w.insert(v[i]);
        }

        if (nr % 2){
            cout<<"-1\n";
            for (i=1;i<=m;i++)
                mrk[v[i]]--;
            continue;
        }

        sol = n + m - 2 + sum;

        for (auto it : w){

            if (frunza[it]){
                if (mrk[it] % 2 == 0)
                    update_heavy (it,rad);
            } else {
                if (mrk[it] % 2)
                    update_heavy (it,rad);
            }

        }

        /*if (m == 2){
            for (i=1;i<=nr_chains;i++)
                cout<<aint[i][1].cnt<<" ";
            cout<<endl;
        }*/

        //for (i=1;i<=nr_chains;i++) /// o sa mi iau tle pe asta da csf
          //  sol += aint[i][1].cnt;

        cout<<sol<<"\n";

        /// reintializez vectorul si refac aintul
        for (auto it : w){

            if (frunza[it]){
                if (mrk[it] % 2 == 0)
                    update_heavy (it,rad);
            } else {
                if (mrk[it] % 2)
                    update_heavy (it,rad);
            }

        }
        for (i=1;i<=m;i++)
            mrk[v[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