Submission #13256

#	Time	Username	Problem	Language	Result	Execution time	Memory
13256		baneling100	Shymbulak (IZhO14_shymbulak)	C++98	91.67 / 100	138 ms	21316 KiB

shymbulak

#include <stdio.h>
#include <vector>
#include <deque>
#define N_MAX 200000

using namespace std;

struct path {
    int dist;
    long long cnt;
} Depth[N_MAX+1], Ans;
vector <int> Road[N_MAX+1];
deque <path> Deq;
int N, C, K, Cycle[N_MAX+2], Check[N_MAX+1];

int findCycle(int now, int prev) {

    int i, j=Road[now].size(), isCycle=0;

    Check[now]=1;
    for(i=0 ; i<j ; i++) {
        if(Check[Road[now][i]]) {
            if(Road[now][i]!=prev) {
                isCycle=Road[now][i];
                break;
            }
        }
        else {
            isCycle=findCycle(Road[now][i],now);
            if(isCycle)
                break;
        }
    }
    Check[now]=0;
    if(isCycle>0) {
        Cycle[++C]=now;
        if(now==isCycle)
            return -1;
    }
    return isCycle;
}

path getDepth(int now) {

    int i, j=Road[now].size(), max2=0;
    long long sum=0, num1, num2=1;
    path x, max1={0,1};
    vector <long long> cnt;

    Check[now]=1;
    cnt.push_back(1);
    for(i=0 ; i<j ; i++)
        if(!Check[Road[now][i]]) {
            x=getDepth(Road[now][i]);
            if(max1.dist<x.dist) {
                if(max1.dist!=max2) {
                    max2=max1.dist;
                    cnt.clear();
                }
                cnt.push_back(max1.cnt);
                max1=x;
            }
            else if(max2<x.dist) {
                max2=x.dist;
                cnt.clear();
                cnt.push_back(x.cnt);
            }
            else if(max2==x.dist)
                cnt.push_back(x.cnt);
        }
    Check[now]=0;
    j=cnt.size();
    for(i=0 ; i<j ; i++)
        sum+=cnt[i];
    num1=max1.cnt*sum;
    if(max1.dist)
        num2=max1.cnt;
    if(max1.dist==max2)
        for(i=0 ; i<j ; i++) {
            sum-=cnt[i];
            num1+=cnt[i]*sum;
            if(max2)
                num2+=cnt[i];
        }
    if(Ans.dist<max1.dist+max2)
        Ans={max1.dist+max2+1,num1};
    else if(Ans.dist==max1.dist+max2+1)
        Ans.cnt+=num1;
    return {max1.dist+1,num2};
}

int main(void) {

    int i, x, y, prev;

    scanf("%d",&N);
    for(i=1 ; i<=N ; i++) {
        scanf("%d %d",&x,&y);
        Road[x].push_back(y);
        Road[y].push_back(x);
    }
    findCycle(1,0);
    Cycle[0]  =Cycle[C];
    Cycle[C+1]=Cycle[1];
    for(i=1 ; i<=C ; i++) {
        Check[Cycle[i-1]]=Check[Cycle[i+1]]=1;
        Check[Cycle[i]]=0;
        Depth[i]=getDepth(Cycle[i]);
    }
    K=C/2;
    for(i=C-K+1 ; i<=C ; i++) {
        while(!Deq.empty() && Deq.back().dist<Depth[i].dist+C-i+1)
            Deq.pop_back();
        if(!Deq.empty() && Deq.back().dist==Depth[i].dist+C-i+1)
            Deq.back().cnt+=Depth[i].cnt;
        else
            Deq.push_back({Depth[i].dist+C-i+1,Depth[i].cnt});
    }
    for(i=1 ; i<=C ; i++) {
        x=Deq.front().dist+Depth[i].dist+i-2;
        y=Deq.front().cnt*Depth[i].cnt;
        if(Ans.dist<x)
            Ans={x,y};
        else if(Ans.dist==x)
            Ans.cnt+=y;
        prev=i-K;
        if(prev<=0)
            prev+=C;
        if(Deq.front().dist+i-K-1==Depth[prev].dist) {
            Deq.front().cnt-=Depth[prev].cnt;
            if(!Deq.front().cnt)
                Deq.pop_front();
        }
        while(!Deq.empty() && Deq.back().dist<Depth[i].dist-i+1)
            Deq.pop_back();
        if(!Deq.empty() && Deq.back().dist==Depth[i].dist-i+1)
            Deq.back().cnt+=Depth[i].cnt;
        else
            Deq.push_back({Depth[i].dist-i+1,Depth[i].cnt});
    }
    printf("%lld",Ans.cnt);

    return 0;
}

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