oj.uz

Submission #304661

# Submission time Handle Problem Language Result Execution time Memory
304661 2020-09-21T17:02:01 Z Ruxandra985 Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 323 ms 33780 KB 
#include <bits/stdc++.h>
#define DIMN 200010
using namespace std;
int sol , x[DIMN];

int lnt,nrc;
int d[DIMN],l[DIMN],poz[DIMN],up[DIMN],f[DIMN],val[DIMN],lvl[DIMN],gr[DIMN];
int cnt[DIMN];
vector <int> v[DIMN],w[DIMN];

struct segm{

    int par, imp , lzy;

};

vector <segm> aint[DIMN];

void precalc (int nod){
    int i,vecin;
    d[nod]=1;
    f[nod]=1;
    cnt[nod] = 0;
    if (v[nod].size() == 1)
        cnt[nod] = 1;

    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (!f[vecin]){
            lvl[vecin]=1+lvl[nod];
            precalc (vecin);
            d[nod]+=d[vecin];
            cnt[nod] += cnt[vecin];

        }
    }
}
void dfs_lant(int nod,int tata){
    int i,vecin,ok=0,maxi,fiu;
    maxi=0;
    fiu=0;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (vecin!=tata){
            ok=1;
            dfs_lant(vecin,nod);
            if (d[vecin]>maxi){
                maxi=d[vecin];
                fiu=vecin;
            }
        }
    }
    if (!ok){ /// frunza
        lnt++;
        l[nod]=lnt; /// lantul din care apartine
        w[lnt].push_back(nod);
    }else { /// unim cu poz
        w[l[fiu]].push_back(nod);
        l[nod]=l[fiu];
        for (i=0;i<v[nod].size();i++){
            vecin=v[nod][i];
            if (vecin!=tata && vecin!=fiu)
                up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului
        }
    }
}

void update_lazy (int lant , int p , int st , int dr){

    if (aint[lant][p].lzy){
        aint[lant][p].lzy = 0;
        swap(aint[lant][p].par , aint[lant][p].imp);

        if (st != dr){

            aint[lant][2 * p].lzy = 1 - aint[lant][2 * p].lzy;
            aint[lant][2 * p + 1].lzy = 1 - aint[lant][2 * p + 1].lzy;

        }
    }


}

void build_aint (int lant,int p,int st,int dr){
    int mid;
    if (st==dr){
        aint[lant][p].par++;
        return;
    }
    mid=(st+dr)/2;
    build_aint(lant,2*p,st,mid);
    build_aint(lant,2*p+1,mid+1,dr);
    aint[lant][p].par = aint[lant][2*p].par + aint[lant][2*p+1].par;
    aint[lant][p].imp = aint[lant][2*p].imp + aint[lant][2*p+1].imp;
}
void update_aint (int lant,int p,int st,int dr,int px , int py){
    int mid;
    update_lazy(lant , p , st , dr);
    if (px <= st && dr <= py){ /// interval ok
        /// in tot intervalul asta are loc schimbul de stari
        aint[lant][p].lzy = 1 - aint[lant][p].lzy;
        update_lazy(lant , p , st , dr);
        return;
    }
    mid=(st+dr)/2;

    if (px<=mid)
        update_aint(lant,2*p,st,mid,px , py);
    if (mid + 1 <= py)
        update_aint(lant,2*p+1,mid+1,dr,px , py);

    update_lazy(lant , 2 * p , st , mid);
    update_lazy(lant , 2 * p + 1 , mid + 1 , dr);

    aint[lant][p].par = aint[lant][2*p].par + aint[lant][2*p+1].par;
    aint[lant][p].imp = aint[lant][2*p].imp + aint[lant][2*p+1].imp;
}
void update (int x,int y){
    /// pe lantul de la x la y, fiecare nod isi schimba starea proprie
    /// asa ca la un nod de pe lant, scazi
    if (l[x]!=l[y]){ /// avansam
        update(up[l[x]],y);

        sol = sol - aint[l[x]][1].par;

        update_aint(l[x],1,0,w[l[x]].size()-1,0,poz[x]);

        sol = sol + aint[l[x]][1].par;
    }
    else{
        sol = sol - aint[l[x]][1].par;

        update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[x],poz[y]),max(poz[x],poz[y]));

        sol = sol + aint[l[x]][1].par;
    }
}


int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , q , xx , y , d , i , root , frnz = 0 , p , vecin;
    fscanf (fin,"%d%d",&n,&q);
    for (i = 1 ; i < n ; i++){
        fscanf (fin,"%d%d",&xx,&y);
        gr[xx]++;
        gr[y]++;
        v[xx].push_back(y);
        v[y].push_back(xx);
    }
    for (i = 1 ; i <= n ; i++){
        if (gr[i] > 1){
            root = i;
            break;
        }
    }

    precalc(root);
    dfs_lant(root , 0);

    for (i=1;i<=lnt;i++){
        reverse(w[i].begin(),w[i].end());
        p=0;
        for (vector <int> :: iterator j=w[i].begin();j!=w[i].end();j++){
            /// pozitia lui din lantul curent
            vecin=*j;
            poz[vecin]=p;
            p++;
        }
    }
    for (i=1;i<=lnt;i++){
        aint[i].resize(w[i].size()*5);
        nrc=0;
        build_aint(i,1,0,w[i].size()-1);
    }

    for (i = 1 ; i <= n ; i++){
        if (gr[i] == 1){
            frnz++;
            update(i , root);
        }
    }

    sol = 0;

    for (i = 1 ; i <= lnt ; i++){
        update_lazy(i , 1 , 0 , w[i].size() - 1);
        sol += aint[i][1].par;
    }


    for (;q;q--){
        fscanf (fin,"%d",&d);

        for (i = 1 ; i <= d ; i++){
            fscanf (fin,"%d",&x[i]);

            if (gr[x[i]] != 1){
                frnz++;
                update (x[i] , root);
            }

            gr[x[i]]++;



        }

        if (frnz % 2)
            fprintf (fout,"-1\n");
        else {
            //for (i = 1 ; i <= lnt ; i++){
              //  update_lazy(i , 1 , 0 , w[i].size() - 1);
               // sol += aint[i][1].par;
            //}
            fprintf (fout,"%d\n" , sol + n + d - 1 - 1);
        }
        for (i = 1 ; i <= d ; i++){
            gr[x[i]]--;
            if (gr[x[i]] != 1){
                frnz--;
                update (x[i] , root);
            }
        }

    }
    return 0;
}

Compilation message

cleaning.cpp: In function 'void precalc(int)':
cleaning.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (i=0;i<v[nod].size();i++){
      |              ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs_lant(int, int)':
cleaning.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (i=0;i<v[nod].size();i++){
      |              ~^~~~~~~~~~~~~~
cleaning.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (i=0;i<v[nod].size();i++){
      |                  ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:146:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  146 |     fscanf (fin,"%d%d",&n,&q);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
cleaning.cpp:148:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  148 |         fscanf (fin,"%d%d",&xx,&y);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
cleaning.cpp:196:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  196 |         fscanf (fin,"%d",&d);
      |         ~~~~~~~^~~~~~~~~~~~~
cleaning.cpp:199:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  199 |             fscanf (fin,"%d",&x[i]);
      |             ~~~~~~~^~~~~~~~~~~~~~~~
cleaning.cpp:225:24: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  225 |                 update (x[i] , root);
      |                 ~~~~~~~^~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 99 ms 17408 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15360 KB Output is correct
2 Correct 36 ms 15360 KB Output is correct
3 Correct 103 ms 32112 KB Output is correct
4 Correct 115 ms 27120 KB Output is correct
5 Correct 140 ms 32368 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 15736 KB Output is correct
2 Correct 100 ms 15736 KB Output is correct
3 Correct 95 ms 33008 KB Output is correct
4 Correct 243 ms 31600 KB Output is correct
5 Correct 85 ms 31160 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 18048 KB Output is correct
2 Correct 50 ms 17408 KB Output is correct
3 Correct 32 ms 17408 KB Output is correct
4 Correct 28 ms 17536 KB Output is correct
5 Correct 33 ms 18168 KB Output is correct
6 Correct 89 ms 17528 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 24184 KB Output is correct
2 Correct 271 ms 25336 KB Output is correct
3 Correct 160 ms 20216 KB Output is correct
4 Correct 238 ms 25208 KB Output is correct
5 Correct 249 ms 25208 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 30200 KB Output is correct
2 Correct 273 ms 33780 KB Output is correct
3 Correct 308 ms 32628 KB Output is correct
4 Correct 296 ms 31864 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 99 ms 17408 KB Output is correct
3 Correct 34 ms 15360 KB Output is correct
4 Correct 36 ms 15360 KB Output is correct
5 Correct 103 ms 32112 KB Output is correct
6 Correct 115 ms 27120 KB Output is correct
7 Correct 140 ms 32368 KB Output is correct
8 Correct 96 ms 15736 KB Output is correct
9 Correct 100 ms 15736 KB Output is correct
10 Correct 95 ms 33008 KB Output is correct
11 Correct 243 ms 31600 KB Output is correct
12 Correct 85 ms 31160 KB Output is correct
13 Correct 127 ms 18048 KB Output is correct
14 Correct 50 ms 17408 KB Output is correct
15 Correct 32 ms 17408 KB Output is correct
16 Correct 28 ms 17536 KB Output is correct
17 Correct 33 ms 18168 KB Output is correct
18 Correct 89 ms 17528 KB Output is correct
19 Correct 213 ms 24184 KB Output is correct
20 Correct 271 ms 25336 KB Output is correct
21 Correct 160 ms 20216 KB Output is correct
22 Correct 238 ms 25208 KB Output is correct
23 Correct 249 ms 25208 KB Output is correct
24 Correct 293 ms 30200 KB Output is correct
25 Correct 273 ms 33780 KB Output is correct
26 Correct 308 ms 32628 KB Output is correct
27 Correct 296 ms 31864 KB Output is correct
28 Correct 184 ms 24588 KB Output is correct
29 Correct 311 ms 33524 KB Output is correct
30 Correct 145 ms 33648 KB Output is correct
31 Correct 232 ms 33008 KB Output is correct
32 Correct 261 ms 25208 KB Output is correct
33 Correct 254 ms 28664 KB Output is correct
34 Correct 323 ms 32116 KB Output is correct
35 Correct 293 ms 31988 KB Output is correct