Submission #36974

#	Time	Username	Problem	Language	Result	Execution time	Memory
36974		chonka	Shymbulak (IZhO14_shymbulak)	C++98	0 / 100	123 ms	14620 KiB

shymbulak

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std ;

#define MAXN 200007

int n ;
vector < int > v[ MAXN ] ;

int used[ MAXN ] ;

bool fl[ MAXN ] ;
vector < int > cycle ;
int h ;
int term ;

int rdist[ MAXN ] ;
int rways[ MAXN ] ;

int diam[ MAXN ] ;
long long dways[ MAXN ] ;


void find_cycle ( int vertex , int prv ) {
    used[ vertex ] = 1 ;
    int i ;
    int sz = v[ vertex ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        if ( used[ v[ vertex ][ i ] ] == 0 ) {
            find_cycle ( v[ vertex ][ i ] , vertex ) ;
        }
        else if ( used[ v[ vertex ][ i ] ] == 1 ) {
            h = 1 ;
            term = used[ v[ vertex ][ i ] ] ;
        }
        if ( h != 0 ) { break ; }
    }
    if ( h != 0 ) {
        if ( h == 1 ) {
            fl[ vertex ] = true ;
            cycle.push_back ( vertex ) ;
        }
        if ( vertex == term ) { h = 2 ; }
    }
    used[ vertex ] = 2 ;
}


void dfs ( int vertex , int prv ) {
    int i ;
    int sz = v[ vertex ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        if ( fl[ v[ vertex ][ i ] ] == true ) { continue ; }
        dfs ( v[ vertex ][ i ] , vertex ) ;
    }
    rdist[ vertex ] = -1 ;
    rways[ vertex ] = 1 ;
    dways[ vertex ] = 1 ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        if ( fl[ v[ vertex ][ i ] ] == true ) { continue ; }
        if ( rdist[ v[ vertex ][ i ] ] + rdist[ vertex ] + 1 > diam[ vertex ] ) {
            diam[ vertex ] = rdist[ v[ vertex ][ i ] ] + rdist[ vertex ] + 1 ;
            dways[ vertex ] = 0 ;
        }
        if ( rdist[ v[ vertex ][ i ] ] + rdist[ vertex ] + 1 == diam[ vertex ] ) {
            dways[ vertex ] += 1LL * rways[ vertex ] * rways[ v[ vertex ][ i ] ] ;
        }
        if ( rdist[ vertex ] < rdist[ v[ vertex ][ i ] ] + 1 ) {
            rdist[ vertex ] = rdist[ v[ vertex ][ i ] ] + 1 ;
            rways[ vertex ] = 0 ;
        }
        if ( rdist[ vertex ] == rdist[ v[ vertex ][ i ] ] + 1 ) {
            rways[ vertex ] ++ ;
        }
    }
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        if ( fl[ v[ vertex ][ i ] ] == true ) { continue ; }
        if ( diam[ v[ vertex ][ i ] ] > diam[ vertex ] ) {
            diam[ vertex ] = diam[ v[ vertex ][ i ] ] ;
            dways[ vertex ] = 0 ;
        }
        if ( diam[ v[ vertex ][ i ] ] == diam[ vertex ] ) {
            dways[ vertex ] += dways[ v[ vertex ][ i ] ] ;
        }
    }
    if ( rdist[ vertex ] < 0 ) { rdist[ vertex ] = 0 ; }
}

class Tree {
};
Tree w ;


void input ( ) {
    scanf ( "%d" , &n ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        int x , y ;
        scanf ( "%d%d" , &x , &y ) ;
        v[ x ].push_back ( y ) ;
        v[ y ].push_back ( x ) ;
    }
}

void solve ( ) {
    find_cycle ( 1 , -1 ) ;
    int sz = cycle.size ( ) ;
    int i ;
    for ( i = 0 ; i < sz ; i ++ ) {
        dfs ( cycle[ i ] , -1 ) ;
    }
    int ans = 0 ;
    int tm = 1 ;
    for ( i = 0 ; i < sz ; i ++ ) {
        /**
        printf ( "--- %d\n" , cycle[ i ] ) ;
        printf ( "%d %d\n" , rdist[ cycle[ i ] ] , rways[ cycle[ i ] ] ) ;
        printf ( "%d %d\n" , diam[ cycle[ i ] ] , dways[ cycle[ i ] ] ) ;
        **/
        if ( ans < diam[ cycle[ i ] ] ) {
            ans = diam[ cycle[ i ] ] ;
            tm = 0 ;
        }
        if ( ans == diam[ cycle[ i ] ] ) {
            tm += dways[ cycle[ i ] ] ;
        }
    }
    printf ( "%d\n" , tm ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message (stderr)

shymbulak.cpp: In function 'void input()':
shymbulak.cpp:100:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &n ) ;
                         ^
shymbulak.cpp:104:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d" , &x , &y ) ;
                                    ^

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50