oj.uz

Submission #13210

# Submission time Handle Problem Language Result Execution time Memory
13210 2015-02-02T16:59:29 Z dohyun0324 Shymbulak (IZhO14_shymbulak) C++
49 / 100
 134 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].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 && 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-1)/2;i++){add(i); check[arr2[i]]+=arr3[i];}
    for(i=1;i<=w;i++){
        del(i); add(i+(w-1)/2); maxi=arr2[dq[0]];
        check[arr2[i]]-=arr3[i]; check[arr2[i+(w-1)/2]]+=arr3[i+(w-1)/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;
    }
    if(w%2==0)
    {
        for(i=1;i<=w;i++)
        {
            if(i+w/2>w) break;
            if(dap==arr[i]+arr[i+w/2]+w/2) ans+=(ll)arr3[i]*(ll)arr3[i+w/2];
            if(dap<arr[i]+arr[i+w/2]+w/2) ans=(ll)arr3[i]*(ll)arr3[i+w/2], dap=arr[i]+arr[i+w/2]+w/2;
        }
    }
    printf("%lld",ans);
    return 0;
}

Subtask #1
14.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 15648 KB Output isn't correct
2 Correct 0 ms 15648 KB Output is correct
3 Correct 3 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 Incorrect 0 ms 15648 KB Output isn't correct
7 Incorrect 3 ms 15648 KB Output isn't correct
8 Correct 0 ms 15648 KB Output is correct
9 Correct 3 ms 15648 KB Output is correct
10 Correct 3 ms 15648 KB Output is correct
11 Incorrect 0 ms 15648 KB Output isn't correct
12 Incorrect 0 ms 15648 KB Output isn't correct
13 Incorrect 3 ms 15648 KB Output isn't correct
14 Incorrect 0 ms 15648 KB Output isn't correct
15 Incorrect 3 ms 15648 KB Output isn't correct

Subtask #2
10.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 Incorrect 0 ms 15648 KB Output isn't correct
4 Incorrect 0 ms 15648 KB Output isn't correct
5 Incorrect 0 ms 15780 KB Output isn't correct
6 Correct 5 ms 15780 KB Output is correct
7 Correct 4 ms 15780 KB Output is correct
8 Correct 0 ms 15780 KB Output is correct
9 Incorrect 0 ms 15780 KB Output isn't correct
10 Incorrect 6 ms 15780 KB Output isn't correct

Subtask #3
25.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 18552 KB Output is correct
2 Correct 75 ms 18948 KB Output is correct
3 Incorrect 63 ms 20908 KB Output isn't correct
4 Incorrect 44 ms 18816 KB Output isn't correct
5 Incorrect 34 ms 18816 KB Output isn't correct
6 Correct 134 ms 21192 KB Output is correct
7 Correct 84 ms 20268 KB Output is correct
8 Incorrect 97 ms 21984 KB Output isn't correct
9 Incorrect 98 ms 21984 KB Output isn't correct
10 Incorrect 93 ms 22356 KB Output isn't correct
11 Correct 117 ms 22616 KB Output is correct
12 Correct 81 ms 22880 KB Output is correct