oj.uz

답안 #13201

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13201 2015-02-02T14:26:44 Z dohyun0324 관광지 (IZhO14_shymbulak) C++
59 / 100
 143 ms 22100 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[200010],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;
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 14868 KB Output is correct
2 Incorrect 3 ms 14868 KB Output isn't correct
3 Correct 2 ms 14868 KB Output is correct
4 Correct 0 ms 14868 KB Output is correct
5 Incorrect 0 ms 14868 KB Output isn't correct
6 Incorrect 0 ms 14868 KB Output isn't correct
7 Correct 0 ms 14868 KB Output is correct
8 Correct 2 ms 14868 KB Output is correct
9 Incorrect 0 ms 14868 KB Output isn't correct
10 Correct 0 ms 14868 KB Output is correct
11 Correct 0 ms 14868 KB Output is correct
12 Correct 0 ms 14868 KB Output is correct
13 Incorrect 2 ms 14868 KB Output isn't correct
14 Incorrect 0 ms 14868 KB Output isn't correct
15 Correct 0 ms 14868 KB Output is correct

Subtask #2
16.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 14868 KB Output is correct
2 Incorrect 0 ms 14868 KB Output isn't correct
3 Correct 2 ms 14868 KB Output is correct
4 Correct 0 ms 14868 KB Output is correct
5 Correct 2 ms 15000 KB Output is correct
6 Incorrect 0 ms 15000 KB Output isn't correct
7 Correct 2 ms 15000 KB Output is correct
8 Correct 0 ms 15000 KB Output is correct
9 Correct 3 ms 15000 KB Output is correct
10 Correct 0 ms 15000 KB Output is correct

Subtask #3
25.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 17772 KB Output is correct
2 Correct 60 ms 18168 KB Output is correct
3 Runtime error 47 ms 20116 KB Program hung waiting for input
4 Runtime error 33 ms 18032 KB SIGSEGV Segmentation fault
5 Runtime error 25 ms 18032 KB SIGSEGV Segmentation fault
6 Correct 143 ms 20412 KB Output is correct
7 Correct 99 ms 19488 KB Output is correct
8 Runtime error 64 ms 21200 KB SIGSEGV Segmentation fault
9 Correct 114 ms 21204 KB Output is correct
10 Correct 115 ms 21576 KB Output is correct
11 Incorrect 106 ms 21836 KB Output isn't correct
12 Incorrect 91 ms 22100 KB Output isn't correct