Submission #36975

#	Time	Username	Problem	Language	Result	Execution time	Memory
36975		chonka	Shymbulak (IZhO14_shymbulak)	C++98	0 / 100	93 ms	26364 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 {
    public :
    int lazy[ 5 * MAXN ] ;
    int tr[ 5 * MAXN ] ;
    int ways[ 5 * MAXN ] ;

    void merge ( int where ) {
        if ( tr[ 2 * where ] > tr[ 2 * where + 1 ] ) {
            tr[ where ] = tr[ 2 * where ] ;
            ways[ where ] = ways[ 2 * where ] ;
        }
        else if ( tr[ 2 * where ] < tr[ 2 * where + 1 ] ) {
            tr[ where ] = tr[ 2 * where + 1 ] ;
            ways[ where ] = ways[ 2 * where + 1 ] ;
        }
        else {
            tr[ where ] = tr[ 2 * where ] ;
            ways[ where ] = ( ways[ 2 * where ] + ways[ 2 * where + 1 ] ) ;
        }
    }
    void push_lazy ( int where , int IL , int IR ) {
        if ( lazy[ where ] == 0 ) { return ; }
        tr[ where ] += lazy[ where ] ;
        if ( IL != IR ) {
            lazy[ 2 * where ] += lazy[ where ] ;
            lazy[ 2 * where + 1 ] += lazy[ where ] ;
        }
        lazy[ where ] = 0 ;
    }
    void init ( int where , int IL , int IR ) {
        lazy[ where ] = 0 ;
        if ( IL == IR ) {
            tr[ where ] = rdist[ cycle[ IL - 1 ] ] ;
            ways[ where ] = rways[ cycle[ IL - 1 ] ] ;
            tr[ where ] += min ( IL - 1 , (int)cycle.size ( ) - IL + 1 ) ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
        merge ( where ) ;
    }
    void update ( int where , int IL , int IR , int CURL , int CURR , int val ) {
        push_lazy ( where , IL , IR ) ;
        if ( IR < CURL || CURR < IL ) { return ; }
        if ( CURL <= IL && IR <= CURR ) {
            lazy[ where ] += val ;
            push_lazy ( where , IL , IR ) ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        update ( 2 * where , IL , mid , CURL , CURR , val ) ;
        update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , val ) ;
        merge ( where ) ;
    }
    pair < int , int > query ( int where , int IL , int IR , int CURL , int CURR ) {
        if ( IR < IL ) { return make_pair ( 0 , 0 ) ; }
        push_lazy ( where , IL , IR ) ;
        if ( IR < CURL || CURR < IL ) { return make_pair ( 0 , 0 ) ; }
        if ( CURL <= IL && IR <= CURR ) {
            return make_pair ( tr[ where ] , ways[ where ] ) ;
        }
        int mid = ( IL + IR ) / 2 ;
        pair < int , int > ret1 , ret2 ;
        ret1 = query ( 2 * where , IL , mid , CURL , CURR ) ;
        ret2 = query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ;
        if ( ret1.first < ret2.first ) { swap ( ret1 , ret2 ) ; }
        if ( ret1.first == ret2.first ) { ret1.second += ret2.second ; }
        return ret1 ;
    }
};
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 ] ] ) ;
    }
    **/
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( ans < diam[ cycle[ i ] ] ) {
            ans = diam[ cycle[ i ] ] ;
            tm = 0 ;
        }
        if ( ans == diam[ cycle[ i ] ] ) {
            tm += dways[ cycle[ i ] ] ;
        }
    }
    w.init ( 1 , 1 , sz ) ;
    for ( i = 1 ; i <= sz ; i ++ ) {
        pair < int , int > ret1 , ret2 ;
        ret1 = w.query ( 1 , 1 , sz , i + 1 , sz ) ;
        ret2 = w.query ( 1 , 1 , sz , 1 , i - 1 ) ;
        if ( ret1.first < ret2.first ) { swap ( ret1 , ret2 ) ; }
        if ( ret1.first == ret2.first ) { ret1.second += ret2.second ; }
        ret1.first += rdist[ cycle[ i - 1 ] ] ;
        int opp = i + ( n + 1 ) / 2 ;
        if ( opp > n ) { opp -= n ; }
        if ( ( n % 2 ) == 0 ) {
            pair < int , int > ret3 = w.query ( 1 , 1 , sz , opp , opp ) ;
            ret3.first += rdist[ cycle[ i - 1 ] ] ;
            if ( ret1.first == ret3.first ) {
                ret1.second += ret3.second ;
            }
        }
        if ( ans < ret1.first ) {
            ans = ret1.first ;
            tm = 0 ;
        }
        if ( ans == ret1.first ) {
            tm += ret1.second ;
        }

        if ( (sz % 2) == 1 ) {
            if ( i <= opp ) {
                w.update ( 1 , 1 , sz , i + 1 , opp - 1 , -1 ) ;

                w.update ( 1 , 1 , sz , opp + 1 , sz , 1 ) ;
                w.update ( 1 , 1 , sz , 1 , i , 1 ) ;
            }
            else {
                w.update ( 1 , 1 , sz , i + 1 , sz , -1 ) ;
                w.update ( 1 , 1 , sz , 1 , opp - 1 , -1 ) ;

                w.update ( 1 , 1 , sz , opp + 1 , i , 1 ) ;
            }
        }
        else {
            if ( i <= opp ) {
                w.update ( 1 , 1 , sz , i + 1 , opp , -1 ) ;

                w.update ( 1 , 1 , sz , opp + 1 , sz , 1 ) ;
                w.update ( 1 , 1 , sz , 1 , i , 1 ) ;
            }
            else {
                w.update ( 1 , 1 , sz , i + 1 , sz , -1 ) ;
                w.update ( 1 , 1 , sz , 1 , opp , -1 ) ;

                w.update ( 1 , 1 , sz , opp + 1 , i , 1 ) ;
            }
        }
    }
    printf ( "%d\n" , tm ) ;
}

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

Compilation message (stderr)

shymbulak.cpp: In function 'void input()':
shymbulak.cpp:169:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &n ) ;
                         ^
shymbulak.cpp:173: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