Submission #365793

#	Time	Username	Problem	Language	Result	Execution time	Memory
365793		Ruxandra985	Shymbulak (IZhO14_shymbulak)	C++14	100 / 100	215 ms	31404 KiB

shymbulak

#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
int low[DIM],niv[DIM],f[DIM],st[DIM],elem,sol;
int w[DIM];
vector <int> v[DIM],s[DIM];
pair <int , long long> lnt[DIM] , aint[DIM];
int lzy[DIM];

int solmax;
long long nr;

void dfs (int nod,int tata){
    int i,vecin;
    low[nod]=niv[nod];
    st[++elem]=nod;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (vecin!=tata){
            if (!niv[vecin]){
                niv[vecin]=1+niv[nod];
                dfs (vecin,nod);
                low[nod]=min(low[nod],low[vecin]);
                ///VERIFICARE
                if (low[vecin]>=niv[nod]){
                    sol++;
                    do{
                        s[sol].push_back(st[elem]);
                        elem--;
                    }while (st[elem+1]!=vecin);
                    s[sol].push_back(nod);
                }
            }
            else low[nod]=min(low[nod],niv[vecin]);
        }
    }
}

void dfs2 (int nod , int tt){
    int i , vecin;
    lnt[nod] = make_pair(1 , 1);

    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i];
        if (f[vecin] || vecin == tt)
            continue; /// nu

        dfs2(vecin , nod);

        if (lnt[vecin].first + lnt[nod].first > solmax){
            solmax = lnt[vecin].first + lnt[nod].first;
            nr = 2LL * lnt[nod].second * lnt[vecin].second;
        }
        else if (lnt[vecin].first + lnt[nod].first == solmax){
            nr = nr + 2LL * lnt[nod].second * lnt[vecin].second;
        }

        if (lnt[vecin].first + 1 > lnt[nod].first){
            lnt[nod].first = lnt[vecin].first + 1;
            lnt[nod].second = lnt[vecin].second;
        }
        else if (lnt[vecin].first + 1 == lnt[nod].first){
            lnt[nod].second += lnt[vecin].second;
        }
    }
}

inline void lazy_update (int nod,int st,int dr){
    if (!lzy[nod]) /// nu ii trb lazy
        return;
    if (st<dr){ /// nu e frunza
        aint[2 * nod].first += lzy[nod];
        aint[2 * nod + 1].first += lzy[nod];
        lzy[2*nod]+=lzy[nod]; /// pass lazy
        lzy[2*nod+1]+=lzy[nod];
    }
    lzy[nod]=0;
}

void build (int nod , int st , int dr , int len){
    int mid = (st + dr) / 2;

    if (st == dr){
        aint[nod] = make_pair(lnt[w[st]].first + min(st - 1 , len - st + 1) , lnt[w[st]].second);
        return;
    }

    build (2 * nod , st , mid , len);
    build (2 * nod + 1 , mid + 1 , dr , len);

    if (aint[2 * nod].first > aint[2 * nod + 1].first)
        aint[nod] = aint[2 * nod];
    else if (aint[2 * nod].first < aint[2 * nod + 1].first)
        aint[nod] = aint[2 * nod + 1];
    else aint[nod] = make_pair(aint[2 * nod].first , aint[2 * nod].second + aint[2 * nod + 1].second);



}

void query (int nod , int st , int dr , int l , int r , int start){
    int mid = (st + dr) / 2;

    lazy_update (nod,st,dr);
    if (l <= st && dr <= r){

        if (solmax < aint[nod].first + lnt[w[start]].first - 1){
            solmax = aint[nod].first + lnt[w[start]].first - 1;
            nr = aint[nod].second * lnt[w[start]].second;
        }
        else if (solmax == aint[nod].first + lnt[w[start]].first - 1)
            nr += aint[nod].second * lnt[w[start]].second;

        return;
    }

    if (l <= mid)
        query(2 * nod , st , mid , l , r , start);
    if (mid + 1 <= r)
        query(2 * nod + 1 , mid + 1 ,dr , l , r , start);

    lazy_update (2*nod,st,mid);
    lazy_update (2*nod+1,mid+1,dr);

}

void update (int nod , int st , int dr , int l , int r , int val){
    int mid = (st + dr) / 2;

    lazy_update (nod,st,dr);
    if (l <= st && dr <= r){

        lzy[nod] += val;
        aint[nod].first += val;
        lazy_update (nod,st,dr);

        return;
    }

    if (l <= mid)
        update(2 * nod , st , mid , l , r , val);
    if (mid + 1 <= r)
        update(2 * nod + 1 , mid + 1 ,dr , l , r , val);

    lazy_update (2*nod,st,mid);
    lazy_update (2*nod+1,mid+1,dr);

    if (aint[2 * nod].first > aint[2 * nod + 1].first)
        aint[nod] = aint[2 * nod];
    else if (aint[2 * nod].first < aint[2 * nod + 1].first)
        aint[nod] = aint[2 * nod + 1];
    else aint[nod] = make_pair(aint[2 * nod].first , aint[2 * nod].second + aint[2 * nod + 1].second);



}


void upd_fr (int nod , int st , int dr ,int x , int val){
    int mid = (st + dr) / 2;

    lazy_update (nod,st,dr);
    if (st == dr){

        if (val == 1)
            aint[nod].second *= 2;
        else aint[nod].second /= 2;

        return;
    }

    if (x <= mid)
        upd_fr(2 * nod , st , mid , x , val);
    else upd_fr(2 * nod + 1 , mid + 1 ,dr , x , val);

    lazy_update (2*nod,st,mid);
    lazy_update (2*nod+1,mid+1,dr);

    if (aint[2 * nod].first > aint[2 * nod + 1].first)
        aint[nod] = aint[2 * nod];
    else if (aint[2 * nod].first < aint[2 * nod + 1].first)
        aint[nod] = aint[2 * nod + 1];
    else aint[nod] = make_pair(aint[2 * nod].first , aint[2 * nod].second + aint[2 * nod + 1].second);



}


int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , x , y , i , j , len , middle , nod;
    fscanf (fin,"%d",&n);
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    /// pasul 1: gaseste ciclul

    for (i=1;i<=n;i++){
        if (!niv[i]){
            niv[i]=1;
            dfs (i,0);
        }
    }

    /// comp biconexa cu + 2 noduri

    for (i = 1 ; i <= sol ; i++){

        if (s[i].size() > 2){ /// asta !!

            for (j = 0 ; j < s[i].size() ; j++){
                w[j + 1] = s[i][j];
                f[s[i][j]] = 1;
            }

            len = s[i].size();

        }

    }

    for (i = 1 ; i <= len ; i++)
        dfs2(w[i] , 0);

    /// pt fiecare nod din ciclu, construiesti diametrul + lantul maxim
    build (1 , 1 , len , len);

    /// daca distamta maxima = diametru maxim, mai adaugi si frq

    if (len % 2 == 0){ /// cazul cand middle are 2 frecvente
        upd_fr (1 , 1 , len , 1 + len / 2 , 1);

        query (1 , 1 , len , 2 , len , 1);

        middle = 1 + len / 2;


        for (i = 2 ; i <= len ; i++){

            /// updatezi intervale
            nod = i;

            middle++;
            if (middle > len)
                upd_fr (1 , 1 , len , middle - len , 1);
            else
                upd_fr (1 , 1 , len , middle , 1);

            if (middle - 1 > len)
                upd_fr (1 , 1 , len , middle - 1 - len , -1);
            else
                upd_fr (1 , 1 , len , middle - 1 , -1);

            /// intre nod si middle - 1 scazi 1

            if (middle - 1 < len){
                update (1 , 1 , len , nod , middle - 1 , -1);
                update (1 , 1 , len , 1 , nod - 1 , 1);
                update (1 , 1 , len , middle , len , 1);

            }
            else if (middle - 1 == len){
                update (1 , 1 , len , nod , middle - 1 , -1);
                update (1 , 1 , len , 1 , nod - 1 , 1);
            }
            else {
                update (1 , 1 , len , nod , len , -1);
                update (1 , 1 , len , 1 , middle - 1 - len , -1);
                update (1 , 1 , len , middle - len , nod - 1 , 1);

            }


            /// query
            query (1 , 1 , len , 1 , i - 1 , i);

            if (i != len)
                query (1 , 1 , len , i + 1 , len , i);


        }


    }
    else {

        query (1 , 1 , len , 2 , len , 1);
        middle = len / 2 + 1;

        for (i = 2 ; i <= len ; i++){

            /// updatezi intervale
            nod = i;
            middle++;

            if (middle == len){
                update (1 , 1 , len , nod , middle - 1 , -1);

                update (1 , 1 , len , 1 , nod - 1 , 1);
            }
            else if (middle == len + 1){
                update (1 , 1 , len , nod , middle - 1 , -1);
                update (1 , 1 , len , 2 , nod - 1 , 1);
            }
            else if (middle < len){
                update (1 , 1 , len , nod , middle - 1 , -1);
                update (1 , 1 , len , middle + 1 , len , 1);
                update (1 , 1 , len , 1 , nod - 1 , 1);

            }
            else {
                update (1 , 1 , len , nod , len , -1);
                update (1 , 1 , len , 1 , middle - 1 - len , -1);

                update (1 , 1 , len , middle + 1 - len , nod - 1 , 1);

            }


            /// query
            query (1 , 1 , len , 1 , i - 1 , i);

            if (i != len)
                query (1 , 1 , len , i + 1 , len , i);


        }

    }

    nr /= 2;

    fprintf (fout,"%lld",nr);

    return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'void dfs(int, int)':
shymbulak.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (i=0;i<v[nod].size();i++){
      |              ~^~~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(int, int)':
shymbulak.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (i = 0 ; i < v[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:217:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |             for (j = 0 ; j < s[i].size() ; j++){
      |                          ~~^~~~~~~~~~~~~
shymbulak.cpp:195:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  195 |     fscanf (fin,"%d",&n);
      |     ~~~~~~~^~~~~~~~~~~~~
shymbulak.cpp:197:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  197 |         fscanf (fin,"%d%d",&x,&y);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
shymbulak.cpp:283:13: warning: 'len' may be used uninitialized in this function [-Wmaybe-uninitialized]
  283 |             if (i != len)
      |             ^~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50