oj.uz

Submission #13211

# Submission time Handle Problem Language Result Execution time Memory
13211 2015-02-02T17:59:21 Z dohyun0324 Shymbulak (IZhO14_shymbulak) C++
100 / 100
 122 ms 22880 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15648 KB Output is correct
2 Correct 0 ms 15648 KB Output is correct
3 Correct 0 ms 15648 KB Output is correct
4 Correct 0 ms 15648 KB Output is correct
5 Correct 0 ms 15648 KB Output is correct
6 Correct 3 ms 15648 KB Output is correct
7 Correct 0 ms 15648 KB Output is correct
8 Correct 3 ms 15648 KB Output is correct
9 Correct 0 ms 15648 KB Output is correct
10 Correct 0 ms 15648 KB Output is correct
11 Correct 0 ms 15648 KB Output is correct
12 Correct 0 ms 15648 KB Output is correct
13 Correct 0 ms 15648 KB Output is correct
14 Correct 0 ms 15648 KB Output is correct
15 Correct 0 ms 15648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15648 KB Output is correct
2 Correct 0 ms 15648 KB Output is correct
3 Correct 0 ms 15648 KB Output is correct
4 Correct 0 ms 15648 KB Output is correct
5 Correct 2 ms 15780 KB Output is correct
6 Correct 0 ms 15780 KB Output is correct
7 Correct 0 ms 15780 KB Output is correct
8 Correct 2 ms 15780 KB Output is correct
9 Correct 3 ms 15780 KB Output is correct
10 Correct 0 ms 15780 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 18552 KB Output is correct
2 Correct 75 ms 18948 KB Output is correct
3 Correct 39 ms 20904 KB Output is correct
4 Correct 47 ms 18816 KB Output is correct
5 Correct 58 ms 18816 KB Output is correct
6 Correct 118 ms 21192 KB Output is correct
7 Correct 90 ms 20268 KB Output is correct
8 Correct 79 ms 21984 KB Output is correct
9 Correct 102 ms 21984 KB Output is correct
10 Correct 96 ms 22360 KB Output is correct
11 Correct 77 ms 22616 KB Output is correct
12 Correct 122 ms 22880 KB Output is correct