Submission #31408

#	Time	Username	Problem	Language	Result	Execution time	Memory
31408		chonka	Factories (JOI14_factories)	C++98	33 / 100	6000 ms	234880 KiB

factories

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

#define MAXN 500007
#define LOG 20
int n ;

vector < pair < int , int > > v[ MAXN ] ;
long long dist[ MAXN ] ;
int LCA[ MAXN ][ LOG + 1 ] ;
int lvl[ MAXN ] ;

int subtree[ MAXN ] ;

int lst[ MAXN ] ;

int used[ MAXN ] ;
int tot = 0 ;

long long ans[ MAXN ] ;

vector < int > ord ;

int fst[ MAXN ] ;

int dp[ 2 * MAXN ][ LOG + 3 ] ;

int pw_id[ 2 * MAXN ] ;

void init_lca ( ) {
    int i , j ;
    int sz = ord.size ( ) ;
    for ( i = 1 ; i <= sz ; i ++ ) {
        dp[ i ][ 0 ] = ord[ i - 1 ] ;
    }
    for ( j = 1 ; j <= LOG + 1 ; j ++ ) {
        for ( i = 1 ; i + (1<<j) - 1 <= sz ; i ++ ) {
            int nxt = i + (1<<(j-1)) ;
            int u1 , u2 ;
            u1 = dp[ i ][ j - 1 ] ;
            u2 = dp[ nxt ][ j - 1 ] ;
            if ( lvl[ u1 ] < lvl[ u2 ] ) { dp[ i ][ j ] = u1 ; }
            else { dp[ i ][ j ] = u2 ; }
        }
    }
    int val = 1 ;
    int id = 0 ;
    for ( i = 1 ; i <= sz ; i ++ ) {
        while ( 2 * val < i ) { val *= 2 ; id ++ ; }
        pw_id[ i ] = id ;
    }
}

void precalc ( int vertex , int prv ) {
    ord.push_back ( vertex ) ;
    fst[ vertex ] = ord.size ( ) ;
    int i ;
    int sz = v[ vertex ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ].first == prv ) { continue ; }
        lvl[ v[ vertex ][ i ].first ] = lvl[ vertex ] + 1 ;
        dist[ v[ vertex ][ i ].first ] = dist[ vertex ] + v[ vertex ][ i ].second ;
        precalc ( v[ vertex ][ i ].first , vertex ) ;
        ord.push_back ( vertex ) ;
    }
}

void dfs ( int vertex , int prv ) {
    if ( used[ vertex ] == 1 ) { return ; }
    tot ++ ;
    int i ;
    int sz = v[ vertex ].size ( ) ;
    subtree[ vertex ] = 1 ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ].first == prv ) { continue ; }
        if ( used[ v[ vertex ][ i ].first ] != 0 ) { continue ; }
        dfs ( v[ vertex ][ i ].first , vertex ) ;
        subtree[ vertex ] += subtree[ v[ vertex ][ i ].first ] ;
    }
}

int find_centroid ( int vertex , int prv ) {
    int i ;
    int sz = v[ vertex ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ].first == prv ) { continue ; }
        if ( used[ v[ vertex ][ i ].first ] == 0 && subtree[ v[ vertex ][ i ].first ] > ( tot / 2 ) ) {
            return find_centroid ( v[ vertex ][ i ].first , vertex ) ;
        }
    }
    return vertex ;
}

void decompose ( int vertex , int prv ) {
    tot = 0 ;
    dfs ( vertex , -1 ) ;
    int cen = find_centroid ( vertex , -1 ) ;
    lst[ cen ] = prv ;
    used[ cen ] = 1 ;
    int i , sz ;
    sz = v[ cen ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( used[ v[ cen ][ i ].first ] == 0 ) {
            decompose ( v[ cen ][ i ].first , cen ) ;
        }
    }
}
int get_LCA ( int x , int y ) {
    if ( fst[ x ] > fst[ y ] ) { swap ( x , y ) ; }
    int len = ( fst[ y ] - fst[ x ] + 1 ) ;
    int val = pw_id[ len ] ;
    int u1 = dp[ fst[ x ] ][ val ] ;
    int u2 = dp[ fst[ y ] - (1<<val) + 1 ][ val ] ;
    if ( lvl[ u1 ] < lvl[ u2 ] ) { return u1 ; }
    return u2 ;
}

long long get_dist ( int x , int y ) {
    int u = get_LCA ( x , y ) ;
    return ( dist[ x ] + dist[ y ] - 2 * dist[ u ] ) ;
}

void update ( int vertex , int x ) {
    while ( vertex != -1 ) {
        long long cur = get_dist ( vertex , x ) ;
        if ( ans[ vertex ] == -1 ) { ans[ vertex ] = cur ; }
        if ( ans[ vertex ] > cur ) { ans[ vertex ] = cur ; }
        vertex = lst[ vertex ] ;
    }
}

void reset ( int vertex ) {
    while ( vertex != -1 ) {
        ans[ vertex ] = -1 ;
        vertex = lst[ vertex ] ;
    }
}

long long query ( int vertex ) {
    long long ret = -1 ;
    int st = vertex ;
    while ( vertex != -1 ) {
        if ( ans[ vertex ] > -1 ) {
            long long cur = get_dist ( st , vertex ) + ans[ vertex ] ;
            if ( ret == -1 ) { ret = cur ; }
            if ( ret > cur ) { ret = cur ; }
        }
        vertex = lst[ vertex ] ;
    }
    return ret ;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N ;
    int i ;
    for ( i = 0 ; i < N - 1 ; i ++ ) {
        A[ i ] ++ ;
        B[ i ] ++ ;
        v[ A[ i ] ].push_back ( make_pair ( B[ i ] , D[ i ] ) ) ;
        v[ B[ i ] ].push_back ( make_pair ( A[ i ] , D[ i ] ) ) ;
    }
    precalc ( 1 , -1 ) ;
    init_lca ( ) ;
    decompose ( 1 , -1 ) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        ans[ i ] = -1 ;
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    int i ;
    for ( i = 0 ; i < S ; i ++ ) {
        X[ i ] ++ ;
    }
    for ( i = 0 ; i < T ; i ++ ) {
        Y[ i ] ++ ;
    }
    for ( i = 0 ; i < S ; i ++ ) {
        update ( X[ i ] , X[ i ] ) ;
    }
    long long ret = -1 ;
    for ( i = 0 ; i < T ; i ++ ) {
        long long cur = query ( Y[ i ] ) ;
        if ( cur > -1 ) {
            if ( ret == -1 ) { ret = cur ; }
            if ( ret > cur ) { ret = cur ; }
        }
    }
    for ( i = 0 ; i < S ; i ++ ) {
        reset ( X[ i ] ) ;
    }
    return ret ;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67