Submission #31435

#	Time	Username	Problem	Language	Result	Execution time	Memory
31435		chonka	Election Campaign (JOI15_election_campaign)	C++98	100 / 100	519 ms	39240 KiB

election_campaign

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

#define MAXN 100007
#define LOG 19

int n , q ;
vector < int > v[ MAXN ] ;
int LCA[ MAXN ][ LOG + 2 ] ;
int lvl[ MAXN ] ;

vector < int > ord ;

int st[ MAXN ] ;
int en[ MAXN ] ;

struct tuhla {
    int x , y ;
    int val ;
};
tuhla f[ MAXN ] ;
vector < tuhla > p[ MAXN ] ;
long long dp[ MAXN ] ;
long long sm[ MAXN ] ;
long long ans = 0 ;


class Tree {
    public :
    long long tr[ 3 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        tr[ where ] = 0 ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void update ( int where , int IL , int IR , int pos , long long val ) {
        if ( IR < pos || pos < IL ) { return ; }
        tr[ where ] += val ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) {
            update ( 2 * where , IL , mid , pos , val ) ;
        }
        else {
            update ( 2 * where + 1 , mid + 1 , IR , pos , val ) ;
        }
    }
    long long query ( int where , int IL , int IR , int pos ) {
        if ( IR <= pos ) { return tr[ where ] ; }
        if ( pos < IL ) { return 0 ; }
        int mid = ( IL + IR ) / 2 ;
        return ( query ( 2 * where , IL , mid , pos ) + query ( 2 * where + 1 , mid + 1 , IR , pos ) ) ;
    }
};
Tree w ;

void dfs ( int vertex , int prv ) {
    ord.push_back ( vertex ) ;
    st[ vertex ] = ord.size ( ) ;
    int i ;
    int sz = v[ vertex ].size ( ) ;
    if ( prv != -1 ) {
        for ( i = 1 ; i <= LOG ; i ++ ) {
            LCA[ vertex ][ i ] = LCA[ LCA[ vertex ][ i - 1 ] ][ i - 1 ] ;
        }
    }
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        LCA[ v[ vertex ][ i ] ][ 0 ] = vertex ;
        lvl[ v[ vertex ][ i ] ] = lvl[ vertex ] + 1 ;
        dfs ( v[ vertex ][ i ] , vertex ) ;
    }
    en[ vertex ] = ord.size ( ) ;
    en[ vertex ] ++ ;
}

int get_LCA ( int x , int y ) {
    int i ;
    for ( i = LOG ; i >= 0 ; i -- ) {
        if ( lvl[ x ] - (1<<i) >= lvl[ y ] ) {
            x = LCA[ x ][ i ] ;
        }
        if ( lvl[ y ] - (1<<i) >= lvl[ x ] ) {
            y = LCA[ y ][ i ] ;
        }
    }
    for ( i = LOG ; i >= 0 ; i -- ) {
        if ( LCA[ x ][ i ] != LCA[ y ][ i ] ) {
            x = LCA[ x ][ i ] ;
            y = LCA[ y ][ i ] ;
        }
    }
    if ( x != y ) { x = LCA[ x ][ 0 ] ; }
    return x ;
}

void rec ( int vertex , int prv ) {
    int i ;
    int sz = v[ vertex ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        rec ( v[ vertex ][ i ] , vertex ) ;
        dp[ vertex ] += dp[ v[ vertex ][ i ] ] ;
    }
    sm[ vertex ] = dp[ vertex ] ;
    sz = p[ vertex ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        int x = p[ vertex ][ i ].x ;
        int y = p[ vertex ][ i ].y ;
        long long add = 0 ;
        if ( lvl[ x ] > lvl[ y ] ) { swap ( x , y ) ; }
        if ( x == vertex ) {
            add += w.query ( 1 , 1 , n , st[ y ] ) ;
        }
        else {
            add += w.query ( 1 , 1 , n , st[ x ] ) ;
            add += w.query ( 1 , 1 , n , st[ y ] ) ;
        }
        add += p[ vertex ][ i ].val + sm[ vertex ] ;
        if ( dp[ vertex ] < add ) { dp[ vertex ] = add ; }
    }
    if ( ans < dp[ vertex ] ) { ans = dp[ vertex ] ; }
    w.update ( 1 , 1 , n , st[ vertex ] , sm[ vertex ] - dp[ vertex ] ) ;
    w.update ( 1 , 1 , n , en[ vertex ] , -(sm[ vertex ] - dp[ vertex ] ) ) ;
}

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 ( ) {
    dfs ( 1 , -1 ) ;
    scanf ( "%d" , &q ) ;
    int i ;
    w.init ( 1 , 1 , n + 1 ) ;
    for ( i = 1 ; i <= q ; i ++ ) {
        scanf ( "%d%d%d" , &f[ i ].x , &f[ i ].y , &f[ i ].val ) ;
        p[ get_LCA ( f[ i ].x , f[ i ].y ) ].push_back ( f[ i ] ) ;
    }
    rec ( 1 , -1 ) ;
    printf ( "%lld\n" , ans ) ;
}


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

Compilation message (stderr)

election_campaign.cpp: In function 'void input()':
election_campaign.cpp:132:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &n ) ;
                         ^
election_campaign.cpp:136:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d" , &x , &y ) ;
                                    ^
election_campaign.cpp: In function 'void solve()':
election_campaign.cpp:145:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &q ) ;
                         ^
election_campaign.cpp:149:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d%d" , &f[ i ].x , &f[ i ].y , &f[ i ].val ) ;
                                                                  ^

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40