oj.uz

Submission #305046

# Submission time Handle Problem Language Result Execution time Memory
305046 2020-09-22T13:06:03 Z nicolaalexandra Spring cleaning (CEOI20_cleaning) C++14
34 / 100
 1000 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;

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
        aint[chain][nod].cnt = (dr - st + 1) - 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);
    }

    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;
        }



        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;
        }*/

        int sol = n + m - 2;
        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 279 ms 11128 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8824 KB Output is correct
2 Correct 56 ms 8828 KB Output is correct
3 Correct 150 ms 26864 KB Output is correct
4 Correct 195 ms 24176 KB Output is correct
5 Correct 245 ms 30192 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 9264 KB Output is correct
2 Correct 62 ms 9308 KB Output is correct
3 Correct 171 ms 26096 KB Output is correct
4 Correct 275 ms 28016 KB Output is correct
5 Correct 150 ms 24304 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 11768 KB Output is correct
2 Correct 77 ms 10744 KB Output is correct
3 Correct 41 ms 10488 KB Output is correct
4 Correct 36 ms 10616 KB Output is correct
5 Correct 45 ms 11256 KB Output is correct
6 Correct 119 ms 11000 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 18040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 23132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 279 ms 11128 KB Output is correct
3 Correct 55 ms 8824 KB Output is correct
4 Correct 56 ms 8828 KB Output is correct
5 Correct 150 ms 26864 KB Output is correct
6 Correct 195 ms 24176 KB Output is correct
7 Correct 245 ms 30192 KB Output is correct
8 Correct 65 ms 9264 KB Output is correct
9 Correct 62 ms 9308 KB Output is correct
10 Correct 171 ms 26096 KB Output is correct
11 Correct 275 ms 28016 KB Output is correct
12 Correct 150 ms 24304 KB Output is correct
13 Correct 131 ms 11768 KB Output is correct
14 Correct 77 ms 10744 KB Output is correct
15 Correct 41 ms 10488 KB Output is correct
16 Correct 36 ms 10616 KB Output is correct
17 Correct 45 ms 11256 KB Output is correct
18 Correct 119 ms 11000 KB Output is correct
19 Execution timed out 1099 ms 18040 KB Time limit exceeded
20 Halted 0 ms 0 KB -