oj.uz

답안 #13206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13206 2015-02-02T15:55:21 Z dohyun0324 관광지 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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