Submission #359283

#	Time	Username	Problem	Language	Result	Execution time	Memory
359283		nicolaalexandra	Shymbulak (IZhO14_shymbulak)	C++14	100 / 100	153 ms	20592 KiB

shymbulak

#include <bits/stdc++.h>
#define DIM 200010
#define DIMBUFF 7000000
using namespace std;

struct segment_tree{
    int maxi,maxi2;
    long long cnt,cnt2; /// cate noduri din arborele initial
    int lazy;
} aint[DIM*4];

vector <int> L[DIM],s;
deque <int> c;
int viz[DIM],fth[DIM],f[DIM],v[DIM],dist[DIM],p[DIM];
pair <int,int> dp[DIM];
char buff[DIMBUFF];
int n,i,x,y,k,sol,pos;
long long sol_cnt;


void dfs (int nod, int tata){
    viz[nod] = 1;
    s.push_back (nod);
    for (auto vecin : L[nod]){
        if (vecin == tata)
            continue;
        if (!viz[vecin])
            dfs (vecin,nod);
        else {
            if (viz[vecin] == 1){

                int poz = s.size()-1;
                while (poz >= 0 && s[poz] != vecin){
                    v[++k] = s[poz];
                    poz--;
                }
                v[++k] = vecin;
            }}}

    s.pop_back();
    viz[nod] = 2; /// nu mai e in stiva
}

void dfs2 (int nod, int tata){
    fth[nod] = v[i];
    for (auto vecin : L[nod]){
        if (vecin != tata && !f[vecin])
            dfs2 (vecin,nod);
    }

    dp[nod].second = 1;
    for (auto vecin : L[nod]){
        if (vecin == tata || f[vecin])
            continue;

        if (dp[nod].first + dp[vecin].first + 1 > sol){
            sol = dp[nod].first + dp[vecin].first + 1;
            sol_cnt = 1LL * dp[nod].second * dp[vecin].second * 2;
        } else {
            if (dp[nod].first + dp[vecin].first + 1 == sol)
                sol_cnt += 1LL * dp[nod].second * dp[vecin].second * 2;
        }

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


void update_nod (int nod){
    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;

    aint[nod] = aint[fiu_st];

    if (aint[fiu_dr].maxi > aint[nod].maxi){
        aint[nod].maxi2 = aint[nod].maxi;
        aint[nod].cnt2 = aint[nod].cnt;

        aint[nod].maxi = aint[fiu_dr].maxi;
        aint[nod].cnt = aint[fiu_dr].cnt;
    } else {
        if (aint[fiu_dr].maxi == aint[nod].maxi)
            aint[nod].cnt += aint[fiu_dr].cnt;
        else {
            if (aint[fiu_dr].maxi > aint[nod].maxi2){
                aint[nod].maxi2 = aint[fiu_dr].maxi;
                aint[nod].cnt2 = aint[fiu_dr].cnt;
            } else {
                if (aint[fiu_dr].maxi == aint[nod].maxi2)
                    aint[nod].cnt2 += aint[fiu_dr].cnt;
            }}}

    if (aint[fiu_dr].maxi2 > aint[nod].maxi2){
        aint[nod].maxi2 = aint[fiu_dr].maxi2;
        aint[nod].cnt2 = aint[fiu_dr].cnt2;
    } else {
        if (aint[fiu_dr].maxi2 == aint[nod].maxi2)
            aint[nod].cnt2 += aint[fiu_dr].cnt2;
    }

}

void update_lazy (int nod, int st, int dr){
    if (!aint[nod].lazy)
        return;
    if (st != dr){
        int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
        aint[fiu_st].maxi += aint[nod].lazy;
        aint[fiu_st].maxi2 += aint[nod].lazy;
        aint[fiu_st].lazy += aint[nod].lazy;

        aint[fiu_dr].maxi += aint[nod].lazy;
        aint[fiu_dr].maxi2 += aint[nod].lazy;
        aint[fiu_dr].lazy += aint[nod].lazy;
    }
    aint[nod].lazy = 0;
}

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod].maxi = dist[st];
        aint[nod].cnt = dp[v[st]].second;
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    update_nod (nod);
}

void update (int nod, int st, int dr, int x, int y, int val){
    if (x > y)
        return;

    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        aint[nod].maxi += val;
        aint[nod].maxi2 += val;
        aint[nod].lazy += val;
        update_lazy (nod,st,dr);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val);
    update_lazy (nod<<1,st,mid);
    update_lazy ((nod<<1)|1,mid+1,dr);

    update_nod (nod);
}


int get_nr (){

    while (!(buff[pos] >= '0' && buff[pos] <= '9'))
        pos++;

    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr * 10 + buff[pos] - '0';
        pos++;
    }

    return nr;

}

int modul (int n){
    return max (n,-n);
}

void bfs (int start){
    memset (dist,0,sizeof dist);
    c.clear();
    c.push_back(start);
    dist[start] = 1;
    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        for (auto vecin : L[nod])
            if (!dist[vecin]){
                dist[vecin] = 1 + dist[nod];

                int ok;
                if (modul(p[fth[start]] - p[fth[vecin]]) == k/2)
                    ok = 2;
                else ok = 1;

                if (dist[vecin] > sol){
                    sol = dist[vecin];
                    sol_cnt = ok;
                } else {
                    if (dist[vecin] == sol)
                        sol_cnt += ok;
                }
                c.push_back(vecin);
            }
    }
}

int main (){

    //FILE *fin = fopen ("date.in","r");
    //FILE *fout = fopen ("date.out","w");

    FILE *fin = stdin;
    FILE *fout = stdout;

    fread (buff,1,DIMBUFF,fin);

    n = get_nr();
    for (i=1;i<=n;i++){
        x = get_nr(), y = get_nr();
        L[x].push_back(y);
        L[y].push_back(x);
    }

    dfs (1,0);

    for (i=1;i<=k;i++){
        f[v[i]] = 1;
        p[v[i]] = i;
    }


    sol = -1;
    for (i=1;i<=k;i++)
        dfs2 (v[i],0);

    if (n <= 500 && k % 2 == 0){ /// nu inteleg dc iau wa pe testu 6
        for (i=1;i<=n;i++)
            bfs (i);

        fprintf(fout,"%lld",sol_cnt/2);
        return 0;
    }


    /// distantele
    int st = 2, dr = k, nr = 1;
    while (st < dr){
        dist[st] = dist[dr] = nr;
        nr++;
        st++, dr--;
    }

    if (k % 2 == 0)
        dist[st] = nr;

    for (i=1;i<=k;i++)
        dist[i] += dp[v[i]].first;

    /// trb sa retin doua maxime in aint??

    build (1,1,k);

    /// lg ciclu impara => nu pot sa am mai mult de un drum minim intre doua noduri


    int poz = k / 2 + 1;
    for (i=1;i<=k;i++){
        /// query

        if (aint[1].maxi != dp[v[i]].first){
            if (aint[1].maxi + dp[v[i]].first > sol){
                sol = aint[1].maxi + dp[v[i]].first;
                sol_cnt = 1LL * dp[v[i]].second * aint[1].cnt;
            } else {
                if (aint[1].maxi + dp[v[i]].first == sol)
                    sol_cnt += 1LL * dp[v[i]].second * aint[1].cnt;
            }
        } else {

            if (aint[1].cnt - dp[v[i]].second){

                if (aint[1].maxi * 2 > sol){
                    sol = aint[1].maxi * 2;
                    sol_cnt = 1LL * dp[v[i]].second * (aint[1].cnt - dp[v[i]].second);
                } else {
                    if (aint[1].maxi * 2 == sol)
                        sol_cnt += 1LL * dp[v[i]].second * (aint[1].cnt - dp[v[i]].second);
                }

            } else { /// iau al doilea maxim

                if (dp[v[i]].first + aint[1].maxi2 > sol){
                    sol = dp[v[i]].first + aint[1].maxi2;
                    sol_cnt = 1LL * dp[v[i]].second * aint[1].cnt2;
                } else {
                    if (dp[v[i]].first + aint[1].maxi2 == sol)
                        sol_cnt += 1LL * dp[v[i]].second * aint[1].cnt2;
                }}}


        /// update

        if (k % 2){ /// lg impara
            if (poz >= k/2 + 1){
                update (1,1,k,i+1,poz,-1);
                update (1,1,k,poz+2,k,1);

                if (poz == k)
                    update (1,1,k,2,i,1);
                else update (1,1,k,1,i,1);
            } else {

                update (1,1,k,i+1,k,-1);
                update (1,1,k,poz+2,i,1);
                update (1,1,k,1,poz,-1);

            }
        } else {

            if (poz >= k/2 + 1){
                update (1,1,k,i+1,poz,-1);
                update (1,1,k,poz+1,n,1);
                update (1,1,k,1,i,1);
            } else {
                update (1,1,k,i+1,n,-1);
                update (1,1,k,poz+1,i,1);
                update (1,1,k,1,poz,-1);
            }


        }

        poz++;
        if (poz > k)
            poz = 1;
    }


    /// trebuie sa mai verific si perechile la care pot sa ajung in doua moduri
    if (k % 2 == 0){
        for (i=1;i<=k;i++){
            int poz = i + k/2;
            if (poz > k)
                poz -= k;

            if (dp[v[i]].first + dp[v[poz]].first + k/2 > sol){
                sol = dp[v[i]].first + dp[v[poz]].first + k/2;
                sol_cnt = 1LL * dp[v[i]].second * dp[v[poz]].second;
            } else {
                if (dp[v[i]].first + dp[v[poz]].first + k/2 == sol)
                    sol_cnt += 1LL * dp[v[i]].second * dp[v[poz]].second;
            }
        }
    }


    fprintf(fout,"%lld",sol_cnt/2);
    //cout<<sol_cnt / 2;


    return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:214:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  214 |     fread (buff,1,DIMBUFF,fin);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~

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