oj.uz

Submission #13200

# Submission time Handle Problem Language Result Execution time Memory
13200 2015-02-02T14:22:11 Z dohyun0324 Shymbulak (IZhO14_shymbulak) C++
59 / 100
 148 ms 22880 KB 
#include<stdio.h>
#include<vector>
#include<deque>
using namespace std;
deque<int>dq;
vector<int>con[200010];
int top=-1,s,e,tree[600010],c=1,sum2,gap,sum,pos,cnt,cycle[200010],ans,dap,maxi,p,p1,p2,n,x,y,ch[200010],w,t,arr[200010],arr2[200010],max1,max2,check[400010],arr3[200010];
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+=sum*sum2;
    if(dap<max1+max2+2) dap=max1+max2+2, ans=sum*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;
    }
    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+=cnt*arr3[i];
        if(dap<maxi+arr[i]-i) ans=cnt*arr3[i], dap=maxi+arr[i]-i;
    }
    printf("%d",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 3 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 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 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 3 ms 15780 KB Output isn't correct
7 Correct 5 ms 15780 KB Output is correct
8 Correct 3 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
25.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 18552 KB Output is correct
2 Correct 70 ms 18948 KB Output is correct
3 Runtime error 0 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 Correct 148 ms 21192 KB Output is correct
7 Correct 112 ms 20268 KB Output is correct
8 Runtime error 51 ms 21980 KB SIGSEGV Segmentation fault
9 Correct 95 ms 21984 KB Output is correct
10 Correct 85 ms 22356 KB Output is correct
11 Incorrect 115 ms 22616 KB Output isn't correct
12 Incorrect 110 ms 22880 KB Output isn't correct