Submission #31409

#	Time	Username	Problem	Language	Result	Execution time	Memory
31409		chonka	Factories (JOI14_factories)	C++98	100 / 100	4943 ms	221740 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 ][ LOG + 1 ] ;
int LCA[ MAXN ][ LOG + 1 ] ;
int lvl[ MAXN ] ;

int subtree[ MAXN ] ;
int lst[ MAXN ] ;
int used[ MAXN ] ;
int tot = 0 ;

long long ans[ MAXN ] ;

int w[ MAXN ] ;

void dfs ( int vertex , int prv , int ori ) {
    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 ; }
        dist[ v[ vertex ][ i ].first ][ w[ ori ] ] = dist[ vertex ][ w[ ori ] ] + v[ vertex ][ i ].second ;
        dfs ( v[ vertex ][ i ].first , vertex , ori ) ;
        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 ;
    if ( prv == -1 ) {
        dfs ( vertex , -1 , 0 ) ;
    }
    else {
        dfs ( vertex , -1 , prv ) ;
    }
    int cen = find_centroid ( vertex , -1 ) ;
    lst[ cen ] = prv ;
    used[ cen ] = 1 ;
    if ( prv != -1 ) {
        w[ cen ] = w[ prv ] + 1 ;
    }
    else {
        w[ cen ] = 1 ;
    }
    int i , sz ;
    sz = v[ cen ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( used[ v[ cen ][ i ].first ] == 0 ) {
            dist[ v[ cen ][ i ].first ][ w[ cen ] ] = v[ cen ][ i ].second ;
            decompose ( v[ cen ][ i ].first , cen ) ;
        }
    }
}


void update ( int vertex , int x ) {
    while ( vertex != -1 ) {
        long long cur = dist[ x ][ w[ vertex ] ] ;
        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 , int x ) {
    long long ret = -1 ;
    while ( vertex != -1 ) {
        if ( ans[ vertex ] > -1 ) {
            long long cur = dist[ x ][ w[ 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 ] ) ) ;
    }
    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 ] , 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: 67 / 67