oj.uz

Submission #13256

# Submission time Handle Problem Language Result Execution time Memory
13256 2015-02-05T22:17:25 Z baneling100 Shymbulak (IZhO14_shymbulak) C++
91.67 / 100
 138 ms 21316 KB 
#include <stdio.h>
#include <vector>
#include <deque>
#define N_MAX 200000

using namespace std;

struct path {
    int dist;
    long long cnt;
} Depth[N_MAX+1], Ans;
vector <int> Road[N_MAX+1];
deque <path> Deq;
int N, C, K, Cycle[N_MAX+2], Check[N_MAX+1];

int findCycle(int now, int prev) {

    int i, j=Road[now].size(), isCycle=0;

    Check[now]=1;
    for(i=0 ; i<j ; i++) {
        if(Check[Road[now][i]]) {
            if(Road[now][i]!=prev) {
                isCycle=Road[now][i];
                break;
            }
        }
        else {
            isCycle=findCycle(Road[now][i],now);
            if(isCycle)
                break;
        }
    }
    Check[now]=0;
    if(isCycle>0) {
        Cycle[++C]=now;
        if(now==isCycle)
            return -1;
    }
    return isCycle;
}

path getDepth(int now) {

    int i, j=Road[now].size(), max2=0;
    long long sum=0, num1, num2=1;
    path x, max1={0,1};
    vector <long long> cnt;

    Check[now]=1;
    cnt.push_back(1);
    for(i=0 ; i<j ; i++)
        if(!Check[Road[now][i]]) {
            x=getDepth(Road[now][i]);
            if(max1.dist<x.dist) {
                if(max1.dist!=max2) {
                    max2=max1.dist;
                    cnt.clear();
                }
                cnt.push_back(max1.cnt);
                max1=x;
            }
            else if(max2<x.dist) {
                max2=x.dist;
                cnt.clear();
                cnt.push_back(x.cnt);
            }
            else if(max2==x.dist)
                cnt.push_back(x.cnt);
        }
    Check[now]=0;
    j=cnt.size();
    for(i=0 ; i<j ; i++)
        sum+=cnt[i];
    num1=max1.cnt*sum;
    if(max1.dist)
        num2=max1.cnt;
    if(max1.dist==max2)
        for(i=0 ; i<j ; i++) {
            sum-=cnt[i];
            num1+=cnt[i]*sum;
            if(max2)
                num2+=cnt[i];
        }
    if(Ans.dist<max1.dist+max2)
        Ans={max1.dist+max2+1,num1};
    else if(Ans.dist==max1.dist+max2+1)
        Ans.cnt+=num1;
    return {max1.dist+1,num2};
}

int main(void) {

    int i, x, y, prev;

    scanf("%d",&N);
    for(i=1 ; i<=N ; i++) {
        scanf("%d %d",&x,&y);
        Road[x].push_back(y);
        Road[y].push_back(x);
    }
    findCycle(1,0);
    Cycle[0]  =Cycle[C];
    Cycle[C+1]=Cycle[1];
    for(i=1 ; i<=C ; i++) {
        Check[Cycle[i-1]]=Check[Cycle[i+1]]=1;
        Check[Cycle[i]]=0;
        Depth[i]=getDepth(Cycle[i]);
    }
    K=C/2;
    for(i=C-K+1 ; i<=C ; i++) {
        while(!Deq.empty() && Deq.back().dist<Depth[i].dist+C-i+1)
            Deq.pop_back();
        if(!Deq.empty() && Deq.back().dist==Depth[i].dist+C-i+1)
            Deq.back().cnt+=Depth[i].cnt;
        else
            Deq.push_back({Depth[i].dist+C-i+1,Depth[i].cnt});
    }
    for(i=1 ; i<=C ; i++) {
        x=Deq.front().dist+Depth[i].dist+i-2;
        y=Deq.front().cnt*Depth[i].cnt;
        if(Ans.dist<x)
            Ans={x,y};
        else if(Ans.dist==x)
            Ans.cnt+=y;
        prev=i-K;
        if(prev<=0)
            prev+=C;
        if(Deq.front().dist+i-K-1==Depth[prev].dist) {
            Deq.front().cnt-=Depth[prev].cnt;
            if(!Deq.front().cnt)
                Deq.pop_front();
        }
        while(!Deq.empty() && Deq.back().dist<Depth[i].dist-i+1)
            Deq.pop_back();
        if(!Deq.empty() && Deq.back().dist==Depth[i].dist-i+1)
            Deq.back().cnt+=Depth[i].cnt;
        else
            Deq.push_back({Depth[i].dist-i+1,Depth[i].cnt});
    }
    printf("%lld",Ans.cnt);

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10960 KB Output is correct
2 Correct 0 ms 10960 KB Output is correct
3 Correct 0 ms 10960 KB Output is correct
4 Correct 0 ms 10960 KB Output is correct
5 Correct 0 ms 10960 KB Output is correct
6 Correct 0 ms 10960 KB Output is correct
7 Correct 0 ms 10960 KB Output is correct
8 Correct 0 ms 10960 KB Output is correct
9 Correct 0 ms 10960 KB Output is correct
10 Correct 1 ms 10960 KB Output is correct
11 Correct 0 ms 10960 KB Output is correct
12 Correct 0 ms 10960 KB Output is correct
13 Correct 0 ms 10960 KB Output is correct
14 Correct 0 ms 10960 KB Output is correct
15 Correct 0 ms 10960 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10960 KB Output is correct
2 Correct 0 ms 10960 KB Output is correct
3 Correct 2 ms 10960 KB Output is correct
4 Correct 0 ms 10960 KB Output is correct
5 Correct 0 ms 11092 KB Output is correct
6 Correct 4 ms 11276 KB Output is correct
7 Correct 0 ms 11092 KB Output is correct
8 Correct 0 ms 11092 KB Output is correct
9 Correct 0 ms 11092 KB Output is correct
10 Correct 0 ms 11092 KB Output is correct

Subtask #3
41.667 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 13864 KB Output isn't correct
2 Correct 75 ms 14260 KB Output is correct
3 Correct 64 ms 17256 KB Output is correct
4 Correct 38 ms 14128 KB Output is correct
5 Correct 53 ms 14128 KB Output is correct
6 Incorrect 138 ms 16504 KB Output isn't correct
7 Correct 102 ms 15580 KB Output is correct
8 Correct 99 ms 17296 KB Output is correct
9 Correct 106 ms 17296 KB Output is correct
10 Correct 97 ms 17748 KB Output is correct
11 Correct 115 ms 21004 KB Output is correct
12 Correct 107 ms 21316 KB Output is correct