Submission #13211

#	Time	Username	Problem	Language	Result	Execution time	Memory
13211		dohyun0324	Shymbulak (IZhO14_shymbulak)	C++98	100 / 100	122 ms	22880 KiB

shymbulak

#include<stdio.h>
#include<vector>
#include<deque>
using namespace std;
typedef long long ll;
deque<int>dq;
vector<int>con[200010];
int top=-1,pos,cnt,cycle[200010],dap,maxi,p,p1,p2,n,x,y,ch[400010],w,t,arr[200010],arr2[400010],max1,max2,check[400010],arr3[400010];
ll sum,sum2,ans,gap;
struct data{
    int maxi,cnt;
}d[200010];
void dfs(int x,int prev)
{
    int i;
    ch[x]=1;
    for(i=0;i<con[x].size();i++){
        if(con[x][i]==prev) continue;
        if(ch[con[x][i]]){
            cycle[++w]=x; t=con[x][i];
            return;
        }
        dfs(con[x][i],x);
        if(t){
            if(t==x) t=0;
            cycle[++w]=x;
            return;
        }
    }
}
void dfs2(int x,int prev)
{
    int i;
    for(i=0;i<con[x].size();i++){
        if(con[x][i]==prev || con[x][i]==p1 || con[x][i]==p2) continue;
        dfs2(con[x][i],x);
        if(d[x].maxi==d[con[x][i]].maxi+1) d[x].cnt+=d[con[x][i]].cnt;
        if(d[x].maxi<d[con[x][i]].maxi+1){
            d[x].maxi=d[con[x][i]].maxi+1; d[x].cnt=d[con[x][i]].cnt;
        }
    }
    max1=-1; max2=-1; pos=-1; sum=0; gap=0; sum2=0;
    for(i=0;i<con[x].size();i++){
        if(con[x][i]==prev || con[x][i]==p1 || con[x][i]==p2) continue;
        if(max1<d[con[x][i]].maxi) max1=d[con[x][i]].maxi, pos=i;
    }
    for(i=0;i<con[x].size();i++){
        if(con[x][i]==prev || con[x][i]==p1 || con[x][i]==p2) continue;
        if(max1==d[con[x][i]].maxi) sum+=d[con[x][i]].cnt;
        if(max2<d[con[x][i]].maxi && pos!=i) max2=d[con[x][i]].maxi;
    }
    if(pos==-1){d[x].cnt=1; return;}
    if(max2==-1){
        if(dap==max1+1) ans+=d[con[x][p]].cnt;
        if(dap<max1+1) dap=max1+1, ans=d[con[x][p]].cnt;
        return;
    }
    if(max1==max2){
        for(i=0;i<con[x].size();i++){
            if(con[x][i]==prev || con[x][i]==p1 || con[x][i]==p2) continue;
            if(max1==d[con[x][i]].maxi) gap+=(ll)d[con[x][i]].cnt*ll(sum-d[con[x][i]].cnt);
        }
        gap/=2;
        if(dap==max1*2+2) ans+=gap;
        if(dap<max1*2+2) dap=max1*2+2, ans=gap;
        return;
    }
    for(i=0;i<con[x].size();i++){
        if(con[x][i]==prev || con[x][i]==p1 || con[x][i]==p2) continue;
        if(max2==d[con[x][i]].maxi) sum2+=d[con[x][i]].cnt;
    }
    if(dap==max1+max2+2) ans+=(ll)sum*(ll)sum2;
    if(dap<max1+max2+2) dap=max1+max2+2, ans=(ll)sum*(ll)sum2;
}
void add(int x)
{
    while(top>=0 && arr2[dq[top]]<=arr2[x]){
        top--; dq.pop_back();
    }
    top++; dq.push_back(x);
}
void del(int x)
{
    if(dq[0]==x) dq.pop_front(), top--;
}
int main()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d %d",&x,&y);
        con[x].push_back(y); con[y].push_back(x);
    }
    dfs(1,0); cycle[0]=cycle[w]; cycle[w+1]=cycle[1];
    for(i=1;i<=w;i++){
        p1=cycle[i-1]; p2=cycle[i+1];
        dfs2(cycle[i],0); arr[i]=d[cycle[i]].maxi; arr3[i]=d[cycle[i]].cnt;
    }
    for(i=1;i<=w;i++) arr2[i]=arr2[i+w]=arr[i]+i, arr2[i+w]+=w, arr3[i+w]=arr3[i];
    maxi=0;
    for(i=1;i<=w/2;i++){add(i); check[arr2[i]]+=arr3[i];}
    for(i=1;i<=w;i++){
        del(i); add(i+w/2); maxi=arr2[dq[0]];
        check[arr2[i]]-=arr3[i]; check[arr2[i+w/2]]+=arr3[i+w/2];
        cnt=check[maxi];
        if(dap==maxi+arr[i]-i) ans+=(ll)cnt*(ll)arr3[i];
        if(dap<maxi+arr[i]-i) ans=(ll)cnt*(ll)arr3[i], dap=maxi+arr[i]-i;
    }
    printf("%lld",ans);
    return 0;
}

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