Submission #545198

#	Time	Username	Problem	Language	Result	Execution time	Memory
545198		chonka	Construction of Highway (JOI18_construction)	C++98	100 / 100	862 ms	28656 KiB

construction

#include<bits/stdc++.h>
using namespace std ;

#define MAXN 100007
#define LOG 20

int n ;
int a[ MAXN ] ;
pair < int , int > edges[ MAXN ] ;
vector < int > v[ MAXN ] ;

int pos_in_tree[ MAXN ] ;
int LCA[ MAXN ][ LOG ] ;
int subtree[ MAXN ] , heavy[ MAXN ] ;
int root[ MAXN ] ;

void dfs ( int vertex ) {
    for ( int i = 1 ; i < LOG ; ++ i ) {
        LCA[ vertex ][ i ] = LCA[ LCA[ vertex ][ i - 1 ] ][ i - 1 ] ;
    }
    subtree[ vertex ] = 1 ;
    int mx = -1 ;
    heavy[ vertex ] = 0 ;
    for ( auto x : v[ vertex ] ) {
        LCA[ x ][ 0 ] = vertex ;
        dfs ( x ) ;
        subtree[ vertex ] += subtree[ x ] ;
        if ( mx < subtree[ x ] ) {
            mx = subtree[ x ] ;
            heavy[ vertex ] = x ;
        }
    }
}

class Tree {
public :
    int tr[ 4 * MAXN ] , lazy[ 4 * MAXN ] ;
    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 ) {
        tr[ where ] = lazy[ 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 CURL , int CURR , int nw ) {
        push_lazy ( where , IL , IR ) ;
        if ( IL > IR || CURL > CURR ) { return ; }
        if ( IR < CURL || CURR < IL ) { return ; }
        if ( CURL <= IL && IR <= CURR ) {
            lazy[ where ] = nw ;
            push_lazy ( where , IL , IR ) ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        update ( 2 * where , IL , mid , CURL , CURR , nw ) ;
        update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , nw ) ;
    }
    int query ( int where , int IL , int IR , int pos ) {
        push_lazy ( where , IL , IR ) ;
        if ( IL == IR ) { return tr[ where ] ; }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) { return query ( 2 * where , IL , mid , pos ) ; }
        return query ( 2 * where + 1 , mid + 1 , IR , pos ) ;
    }
};
Tree w ;

void input ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    for ( int i = 1 ; i < n ; ++ i ) {
        cin >> edges[ i ].first >> edges[ i ].second ;
        v[ edges[ i ].first ].push_back ( edges[ i ].second ) ;
    }
}
stack < pair < int , int > > s ;

pair < int , int > srt[ MAXN ] ;
pair < int , int > aux[ MAXN ] ;

long long f ( int l , int r ) {
    if ( l == r ) { return 0 ; }
    int mid = ( l + r ) / 2 ;
    long long ret = f ( l , mid ) + f ( mid + 1 , r ) ;
    int pos1 , pos2 ;
    pos1 = l , pos2 = mid + 1 ;
    int tp = l - 1 ;
    long long sm_l = 0 ;
    for ( int i = l ; i <= mid ; ++ i ) {
        sm_l += srt[ i ].second ;
    }
    while ( pos1 <= mid || pos2 <= r ) {
        if ( pos1 > mid ) {
            aux[ ++ tp ] = srt[ pos2 ++ ] ;
        }
        else if ( pos2 > r ) {
            aux[ ++ tp ] = srt[ pos1 ++ ] ;
        }
        else {
            if ( srt[ pos1 ].first <= srt[ pos2 ].first ) {
                aux[ ++ tp ] = srt[ pos1 ] ;
                sm_l -= srt[ pos1 ++ ].second ;
            }
            else {
                aux[ ++ tp ] = srt[ pos2 ] ;
                ret += srt[ pos2 ++ ].second * sm_l ;
            }
        }
    }
    for ( int i = l ; i <= r ; ++ i ) {
        srt[ i ] = aux[ i ] ;
    }
    return ret ;
}

void solve ( ) {
    dfs ( 1 ) ;
    int tp = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( heavy[ LCA[ i ][ 0 ] ] != i ) {
            int x = i ;
            while ( x != 0 ) {
                pos_in_tree[ x ] = ++ tp ;
                root[ x ] = i ;
                x = heavy[ x ] ;
            }
        }
    }
    w.init ( 1 , 1 , n ) ;
    w.update ( 1 , 1 , n , 1 , 1 , 1 ) ;
    for ( int i = 1 ; i < n ; ++ i ) {
        int wh = edges[ i ].first ;
        while ( wh > 0 ) {
            int sr = w.query ( 1 , 1 , n , pos_in_tree[ wh ] ) ;
            int cnt = 1 ;
            for ( int j = LOG - 1 ; j >= 0 ; -- j ) {
                if ( LCA[ wh ][ j ] > 0 && w.query ( 1 , 1 , n , pos_in_tree[ LCA[ wh ][ j ] ] ) == sr ) {
                    wh = LCA[ wh ][ j ] ;
                    cnt += ( 1 << j ) ;
                }
            }
            s.push ( { a[ sr ] , cnt } ) ;
            wh = LCA[ wh ][ 0 ] ;
        }
        tp = 0 ;
        while ( s.empty ( ) == false ) {
            srt[ ++ tp ] = s.top ( ) ;
            s.pop ( ) ;
        }
        cout << f ( 1 , tp ) << "\n" ;
        wh = edges[ i ].second ;
        while ( wh > 0 ) {
            w.update ( 1 , 1 , n , pos_in_tree[ root[ wh ] ] , pos_in_tree[ wh ] , edges[ i ].second ) ;
            wh = LCA[ root[ wh ] ][ 0 ] ;
        }
    }
}


int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    // cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84