oj.uz

Submission #13209

# Submission time Handle Problem Language Result Execution time Memory
13209 2015-02-02T16:15:43 Z dohyun0324 Shymbulak (IZhO14_shymbulak) C++
96 / 100
 110 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/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
26.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 15780 KB Output is correct
6 Correct 2 ms 15780 KB Output is correct
7 Correct 6 ms 15780 KB Output is correct
8 Correct 3 ms 15780 KB Output is correct
9 Correct 2 ms 15780 KB Output is correct
10 Correct 6 ms 15780 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18552 KB Output is correct
2 Correct 58 ms 18948 KB Output is correct
3 Correct 59 ms 20900 KB Output is correct
4 Correct 33 ms 18816 KB Output is correct
5 Correct 58 ms 18816 KB Output is correct
6 Correct 101 ms 21192 KB Output is correct
7 Correct 99 ms 20268 KB Output is correct
8 Correct 98 ms 21984 KB Output is correct
9 Correct 95 ms 21984 KB Output is correct
10 Correct 85 ms 22356 KB Output is correct
11 Correct 110 ms 22616 KB Output is correct
12 Correct 91 ms 22880 KB Output is correct