Submission #359264

#	Time	Username	Problem	Language	Result	Execution time	Memory
359264		nicolaalexandra	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	1589 ms	9452 KiB

shymbulak

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

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

vector <int> L[DIM];
vector <pair<int,int> > w;
int viz[DIM],fth[DIM],f[DIM],v[DIM],dist[DIM];
pair <int,int> dp[DIM];
int n,i,x,y,k,sol,sol_cnt;

void dfs (int nod, int tata){

    viz[nod] = 1;
    fth[nod] = tata;
    for (auto vecin : L[nod]){

        if (!viz[vecin])
            dfs (vecin,nod);
        else {
            if (vecin != tata && !k){
                int x = nod;
                while (x != vecin){
                    v[++k] = x;
                    x = fth[x];
                }
                v[++k] = vecin;
            }}}}

void dfs2 (int nod, int tata){

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

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

        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;
        }


        w.push_back(make_pair(dp[vecin].first+1,dp[vecin].second));

    }

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

    /// verific si drumurile care au lca in nod

    sort (w.begin(),w.end());

    if (w.size() >= 2){
        int val = w.back().first, cnt = w.back().second, nr = 0;
        for (int i=w.size()-2;i>=0;i--){
            if (w[i].first == val){
                nr += cnt * w[i].second;
                cnt += w[i].second;
            } else break;
        }

        if (nr){
            if (val * 2 > sol)
                sol = val * 2, sol_cnt = nr * 2; /// numar perechile de doua ori
            else {
                if (val * 2 == sol)
                    sol_cnt += nr * 2;
            }
        } else {

            int cnt = 0, val = w[w.size()-2].first;
            for (i=w.size()-2;i>=0;i--){
                if (w[i].first == val)
                    cnt += w[i].second;
                else break;
            }

            if (w.back().first + val > sol){
                sol = w.back().first + val;
                sol_cnt = w.back().second * cnt * 2;
            } else {
                if (w.back().first + val == sol)
                    sol_cnt += w.back().second * cnt * 2;
            }}}}

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 main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

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

    dfs (1,0);

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

    for (i=1;i<=k;i++)
        dfs2 (v[i],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);

    if (k % 2){ /// 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 = dp[v[i]].second * aint[1].cnt;
                } else {
                    if (aint[1].maxi + dp[v[i]].first == sol)
                        sol_cnt += 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 = dp[v[i]].second * (aint[1].cnt - dp[v[i]].second);
                    } else {
                        if (aint[1].maxi * 2 == sol)
                            sol_cnt += 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 = dp[v[i]].second * aint[1].cnt2;
                    } else {
                        if (dp[v[i]].first + aint[1].maxi2 == sol)
                            sol_cnt += dp[v[i]].second * aint[1].cnt2;
                    }
                }
            }


            /// update
            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);

            }

            poz++;
            if (poz > k)
                poz = 1;
        }
    } else { /// lg para

        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 = dp[v[i]].second * aint[1].cnt;
                } else {
                    if (aint[1].maxi + dp[v[i]].first == sol)
                        sol_cnt += 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 = dp[v[i]].second * (aint[1].cnt - dp[v[i]].second);
                    } else {
                        if (aint[1].maxi * 2 == sol)
                            sol_cnt += 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 = dp[v[i]].second * aint[1].cnt2;
                    } else {
                        if (dp[v[i]].first + aint[1].maxi2 == sol)
                            sol_cnt += dp[v[i]].second * aint[1].cnt2;
                    }
                }
            }

            /// update
            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

        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 = dp[v[i]].second * dp[v[poz]].second;
            } else {
                if (dp[v[i]].first + dp[v[poz]].first + k/2 == sol)
                    sol_cnt += dp[v[i]].second * dp[v[poz]].second;
            }
        }

    }

    cout<<sol_cnt / 2;


    return 0;
}

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