Submission #365793

# Submission time Handle Problem Language Result Execution time Memory
365793 2021-02-12T11:14:29 Z Ruxandra985 Shymbulak (IZhO14_shymbulak) C++14
100 / 100
215 ms 31404 KB
#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

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)
      |             ^~
# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 8 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9708 KB Output is correct
6 Correct 7 ms 9708 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 7 ms 9708 KB Output is correct
9 Correct 7 ms 9708 KB Output is correct
10 Correct 7 ms 9708 KB Output is correct
11 Correct 7 ms 9708 KB Output is correct
12 Correct 7 ms 9708 KB Output is correct
13 Correct 8 ms 9836 KB Output is correct
14 Correct 7 ms 9836 KB Output is correct
15 Correct 7 ms 9836 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 9964 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 8 ms 9984 KB Output is correct
4 Correct 8 ms 9836 KB Output is correct
5 Correct 9 ms 10220 KB Output is correct
6 Correct 9 ms 10220 KB Output is correct
7 Correct 10 ms 10220 KB Output is correct
8 Correct 10 ms 10240 KB Output is correct
9 Correct 9 ms 10220 KB Output is correct
10 Correct 9 ms 10220 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 94 ms 17900 KB Output is correct
2 Correct 95 ms 18668 KB Output is correct
3 Correct 152 ms 24428 KB Output is correct
4 Correct 63 ms 19436 KB Output is correct
5 Correct 67 ms 20096 KB Output is correct
6 Correct 215 ms 27600 KB Output is correct
7 Correct 149 ms 23916 KB Output is correct
8 Correct 121 ms 30188 KB Output is correct
9 Correct 123 ms 30060 KB Output is correct
10 Correct 120 ms 31404 KB Output is correct
11 Correct 132 ms 29152 KB Output is correct
12 Correct 149 ms 30360 KB Output is correct