oj.uz

Submission #13206

# Submission time Handle Problem Language Result Execution time Memory
13206 2015-02-02T15:55:21 Z dohyun0324 Shymbulak (IZhO14_shymbulak) C++
38.17 / 100
 85 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);
    }
    if(n>=100000) return 0;
    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;
    }
    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 0 ms 15648 KB Output is correct
2 Incorrect 3 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 0 ms 15648 KB Output isn't correct
7 Correct 0 ms 15648 KB Output is correct
8 Correct 0 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 0 ms 15648 KB Output is correct
12 Correct 3 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 3 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 3 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 0 ms 15780 KB Output is correct
9 Correct 0 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 52 ms 18552 KB Output is correct
2 Incorrect 63 ms 18944 KB Output isn't correct
3 Incorrect 42 ms 18680 KB Output isn't correct
4 Runtime error 32 ms 18812 KB Program hung waiting for input
5 Incorrect 26 ms 18812 KB Output isn't correct
6 Incorrect 67 ms 21188 KB Output isn't correct
7 Incorrect 67 ms 20264 KB Output isn't correct
8 Incorrect 77 ms 21980 KB Output isn't correct
9 Incorrect 79 ms 21980 KB Output isn't correct
10 Incorrect 83 ms 22244 KB Output isn't correct
11 Incorrect 85 ms 22612 KB Output isn't correct
12 Incorrect 79 ms 22876 KB Output isn't correct