oj.uz

Submission #13257

# Submission time Handle Problem Language Result Execution time Memory
13257 2015-02-05T22:48:17 Z baneling100 Shymbulak (IZhO14_shymbulak) C++
100 / 100
 153 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+1)
        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 2 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 0 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 2 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 3 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 5 ms 11092 KB Output is correct
9 Correct 0 ms 11092 KB Output is correct
10 Correct 2 ms 11092 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 13864 KB Output is correct
2 Correct 73 ms 14260 KB Output is correct
3 Correct 54 ms 17248 KB Output is correct
4 Correct 52 ms 14128 KB Output is correct
5 Correct 56 ms 14128 KB Output is correct
6 Correct 153 ms 16504 KB Output is correct
7 Correct 109 ms 15580 KB Output is correct
8 Correct 117 ms 17296 KB Output is correct
9 Correct 101 ms 17296 KB Output is correct
10 Correct 98 ms 17748 KB Output is correct
11 Correct 113 ms 21004 KB Output is correct
12 Correct 135 ms 21316 KB Output is correct