oj.uz

Submission #305049

# Submission time Handle Problem Language Result Execution time Memory
305049 2020-09-22T13:14:21 Z nicolaalexandra Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 623 ms 30192 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 155 ms 10616 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8440 KB Output is correct
2 Correct 55 ms 8440 KB Output is correct
3 Correct 147 ms 25992 KB Output is correct
4 Correct 190 ms 23024 KB Output is correct
5 Correct 247 ms 28908 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8952 KB Output is correct
2 Correct 59 ms 8824 KB Output is correct
3 Correct 171 ms 24944 KB Output is correct
4 Correct 275 ms 26408 KB Output is correct
5 Correct 150 ms 23412 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 11000 KB Output is correct
2 Correct 70 ms 10360 KB Output is correct
3 Correct 35 ms 10240 KB Output is correct
4 Correct 35 ms 10488 KB Output is correct
5 Correct 40 ms 11000 KB Output is correct
6 Correct 119 ms 10488 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 16888 KB Output is correct
2 Correct 308 ms 18276 KB Output is correct
3 Correct 207 ms 13048 KB Output is correct
4 Correct 294 ms 18172 KB Output is correct
5 Correct 310 ms 18124 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 22524 KB Output is correct
2 Correct 522 ms 26868 KB Output is correct
3 Correct 623 ms 24692 KB Output is correct
4 Correct 520 ms 24312 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 155 ms 10616 KB Output is correct
3 Correct 55 ms 8440 KB Output is correct
4 Correct 55 ms 8440 KB Output is correct
5 Correct 147 ms 25992 KB Output is correct
6 Correct 190 ms 23024 KB Output is correct
7 Correct 247 ms 28908 KB Output is correct
8 Correct 64 ms 8952 KB Output is correct
9 Correct 59 ms 8824 KB Output is correct
10 Correct 171 ms 24944 KB Output is correct
11 Correct 275 ms 26408 KB Output is correct
12 Correct 150 ms 23412 KB Output is correct
13 Correct 126 ms 11000 KB Output is correct
14 Correct 70 ms 10360 KB Output is correct
15 Correct 35 ms 10240 KB Output is correct
16 Correct 35 ms 10488 KB Output is correct
17 Correct 40 ms 11000 KB Output is correct
18 Correct 119 ms 10488 KB Output is correct
19 Correct 330 ms 16888 KB Output is correct
20 Correct 308 ms 18276 KB Output is correct
21 Correct 207 ms 13048 KB Output is correct
22 Correct 294 ms 18172 KB Output is correct
23 Correct 310 ms 18124 KB Output is correct
24 Correct 594 ms 22524 KB Output is correct
25 Correct 522 ms 26868 KB Output is correct
26 Correct 623 ms 24692 KB Output is correct
27 Correct 520 ms 24312 KB Output is correct
28 Correct 267 ms 17536 KB Output is correct
29 Correct 322 ms 26612 KB Output is correct
30 Correct 227 ms 30192 KB Output is correct
31 Correct 276 ms 27884 KB Output is correct
32 Correct 302 ms 18040 KB Output is correct
33 Correct 349 ms 21368 KB Output is correct
34 Correct 402 ms 24564 KB Output is correct
35 Correct 405 ms 24436 KB Output is correct