Submission #304661

#	Time	Username	Problem	Language	Result	Execution time	Memory
304661		Ruxandra985	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	323 ms	33780 KiB

cleaning

#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 (stderr)

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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30