Submission #37236

#	Time	Username	Problem	Language	Result	Execution time	Memory
37236		chonka	Hard route (IZhO17_road)	C++98	0 / 100	16 ms	48896 KiB

road

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

#define MAXN 500007

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

struct tuhla {
    int val ;
    int tm ;
    tuhla ( ) { val = tm = 0 ; }
    tuhla ( int _val , int _tm ) {
        val = _val ;
        tm = _tm ;
    }
};
tuhla dp[ MAXN ] ;
tuhla up[ MAXN ] ;

tuhla ret[ MAXN ][ 7 ] ;
long long ans ;
long long tot ;

vector < int > pos ;

tuhla update ( tuhla cur , int x , int y ) {
    if ( cur.val < x ) { cur.val = x ; cur.tm = 0 ; }
    if ( cur.val == x ) { cur.tm += y ; }
    return cur ;
}

void dfs_down ( int vertex , int prv ) {
    int i ;
    int sz = v[ vertex ].size ( ) ;
    dp[ vertex ] = tuhla ( 0 , 1 ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        dfs_down ( v[ vertex ][ i ] , vertex ) ;
        dp[ vertex ] = update ( dp[ vertex ] , dp[ v[ vertex ][ i ] ].val + 1 , dp[ v[ vertex ][ i ] ].tm ) ;
    }
}
void dfs_up ( int vertex , int prv ) {
    int i ;
    int sz = v[ vertex ].size ( ) ;
    tuhla p1 , p2 ;
    int id1 , id2 ;
    id1 = 0 ;
    id2 = 0 ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        up[ v[ vertex ][ i ] ] = tuhla ( 0 , 1 ) ;
        up[ v[ vertex ][ i ] ] = update ( up[ v[ vertex ][ i ] ] , up[ vertex ].val + 1 , up[ vertex ].tm ) ;
    }
    tuhla cur = tuhla ( -50 , 1 ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        up[ v[ vertex ][ i ] ] = update ( up[ v[ vertex ][ i ] ] , cur.val , cur.tm ) ;
        cur = update ( cur , dp[ v[ vertex ][ i ] ].val + 2 , dp[ v[ vertex ][ i ] ].tm ) ;
    }
    cur = tuhla ( -50 , 1 ) ;
    for ( i = sz - 1 ; i >= 0 ; i -- ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        up[ v[ vertex ][ i ] ] = update ( up[ v[ vertex ][ i ] ] , cur.val , cur.tm ) ;
        cur = update ( cur , dp[ v[ vertex ][ i ] ].val + 2 , dp[ v[ vertex ][ i ] ].tm ) ;
    }
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        dfs_up ( v[ vertex ][ i ] , vertex ) ;
    }
}

void recalc ( tuhla &best1 , tuhla &best2 , tuhla &best3 , int x , int y ) {
    if ( best1.val < x ) {
        best3 = best2 ;
        best2 = best1 ;
        best1 = tuhla ( x , y ) ;
    }
    else if ( best2.val < x ) {
        best3 = best2 ;
        best2 = tuhla ( x , y ) ;
    }
    else {
        best3 = tuhla ( x , y ) ;
    }
}

void get_mx ( int vertex , int prv ) {
    tuhla best1 , best2 , best3 ;
    best1 = tuhla ( -50 , 1 ) ;
    best2 = tuhla ( -50 , 1 ) ;
    best3 = tuhla ( -50 , 1 ) ;
    int i ;
    int sz = v[ vertex ].size ( ) ;
    if ( prv != -1 ) {
        recalc ( best1 , best2 , best3 , up[ vertex ].val , up[ vertex ].tm ) ;
    }
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        recalc ( best1 , best2 , best3 , dp[ v[ vertex ][ i ] ].val + 1 , dp[ v[ vertex ][ i ] ].tm ) ;
    }
    if ( best3.val != -50 ) {
        long long aux = 1LL * best1.val * ( best2.val + best3.val ) ;
        if ( ans < aux ) {
            pos.clear ( ) ;
            ans = aux ;
        }
        if ( ans == aux ) {
            pos.push_back ( vertex ) ;
        }
    }
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        get_mx ( v[ vertex ][ i ] , vertex ) ;
    }
}

long long calc_fixed_len ( int vertex , int len ) {
    int i ;
    long long ret = 0 ;
    int sz = v[ vertex ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( dp[ v[ vertex ][ i ] ].val + 1 == len ) { ret += dp[ v[ vertex ][ i ] ].tm ; }
    }
    return ret ;
}

long long calc_double ( int vertex , int len ) {
    int i ;
    long long ret = 0 ;
    long long sm = 0 ;
    int sz = v[ vertex ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( dp[ v[ vertex ][ i ] ].val + 1 == len ) {
            ret += sm * dp[ v[ vertex ][ i ] ].tm ;
            sm += dp[ v[ vertex ][ i ] ].tm ;
        }
    }
    return ret ;
}

void get_combinations ( int vertex ) {
    dfs_down ( vertex , -1 ) ;
    tuhla best1 , best2 , best3 ;
    best1 = tuhla ( -50 , 1 ) ;
    best2 = tuhla ( -50 , 1 ) ;
    best3 = tuhla ( -50 , 1 ) ;
    int i ;
    int sz = v[ vertex ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        recalc ( best1 , best2 , best3 , dp[ v[ vertex ][ i ] ].val + 1 , dp[ v[ vertex ][ i ] ].tm ) ;
    }
    if ( best1.val != best2.val && best2.val != best3.val ) {
        long long aux1 , aux2 ;
        aux1 = best2.tm ;
        aux2 = calc_fixed_len ( vertex  , best3.val ) ;
        tot += aux1 * aux2 ;
    }
    else if ( best1.val == best2.val && best2.val != best3.val ) {
        long long aux1 , aux2 ;
        aux1 = best1.tm + best2.tm ;
        aux2 = calc_fixed_len ( vertex , best3.val ) ;
        tot += aux1 * aux2 ;
    }
    else {
        tot += calc_double( vertex , best2.val ) ;
    }
}

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 ( ) {
    int i ;
    int leaves = 0 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        leaves += ( v[ i ].size ( ) == 1 ) ;
    }
    if ( leaves == 2 ) { printf ( "0 1\n" ) ; return ; }
    dfs_down ( 1 , -1 ) ;
    up[ 1 ] = tuhla ( 0 , 1 ) ;
    dfs_up ( 1 , -1 ) ;
    get_mx ( 1 , -1 ) ;
    int sz = pos.size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        get_combinations ( pos[ i ] ) ;
    }
    printf ( "%lld %lld\n" , ans , tot ) ;
}

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

Compilation message (stderr)

road.cpp: In function 'void dfs_up(int, int)':
road.cpp:49:9: warning: variable 'id1' set but not used [-Wunused-but-set-variable]
     int id1 , id2 ;
         ^
road.cpp:49:15: warning: variable 'id2' set but not used [-Wunused-but-set-variable]
     int id1 , id2 ;
               ^
road.cpp: In function 'void input()':
road.cpp:173:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &n ) ;
                         ^
road.cpp:177: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 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48