oj.uz

Submission #13205

# Submission time Handle Problem Language Result Execution time Memory
13205 2015-02-02T15:54:31 Z dohyun0324 Shymbulak (IZhO14_shymbulak) C++
38.17 / 100
 128 ms 22876 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,s,e,c=1,sum2,gap,sum,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 ans;
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 lev)
{
    int i;
    if(maxi<lev) maxi=lev, p=x;
    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,lev+1);
        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+=d[con[x][i]].cnt*(sum-d[con[x][i]].cnt);
        }
        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,p;
    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];
        maxi=0; dfs2(cycle[i],0,0); arr[i]=d[cycle[i]].maxi; arr3[i]=d[cycle[i]].cnt;
    }
    if(n>=100000) return 0;
    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
18.0 / 30.0

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

Subtask #2
16.0 / 20.0

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

Subtask #3
4.167 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 18552 KB Output is correct
2 Incorrect 60 ms 18944 KB Output isn't correct
3 Runtime error 54 ms 20896 KB Program hung waiting for input
4 Runtime error 0 ms 18812 KB SIGSEGV Segmentation fault
5 Runtime error 0 ms 18812 KB SIGSEGV Segmentation fault
6 Incorrect 125 ms 21188 KB Output isn't correct
7 Incorrect 95 ms 20264 KB Output isn't correct
8 Runtime error 66 ms 21980 KB SIGSEGV Segmentation fault
9 Incorrect 92 ms 21980 KB Output isn't correct
10 Incorrect 83 ms 22356 KB Output isn't correct
11 Incorrect 79 ms 22612 KB Output isn't correct
12 Incorrect 128 ms 22876 KB Output isn't correct