oj.uz

Submission #31406

# Submission time Handle Problem Language Result Execution time Memory
31406 2017-08-21T10:02:53 Z chonka Factories (JOI14_factories) C++
15 / 100
 6000 ms 114376 KB 
#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 ] ;

void precalc ( int vertex , int prv ) {
    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 ].first == prv ) { continue ; }
        lvl[ v[ vertex ][ i ].first ] = lvl[ vertex ] + 1 ;
        LCA[ v[ vertex ][ i ].first ][ 0 ] = vertex ;
        dist[ v[ vertex ][ i ].first ] = dist[ vertex ] + v[ vertex ][ i ].second ;
        precalc ( v[ vertex ][ i ].first , 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 ) {
    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 ;
}

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 ) ;
    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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 92644 KB Output is correct
2 Correct 2539 ms 92908 KB Output is correct
3 Correct 4022 ms 92908 KB Output is correct
4 Correct 3109 ms 92908 KB Output is correct
5 Correct 5249 ms 92928 KB Output is correct
6 Correct 889 ms 92944 KB Output is correct
7 Correct 3806 ms 92908 KB Output is correct
8 Correct 3666 ms 92908 KB Output is correct
9 Correct 4693 ms 92924 KB Output is correct
10 Correct 756 ms 92944 KB Output is correct
11 Correct 3906 ms 92908 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 92644 KB Output is correct
2 Correct 4849 ms 111388 KB Output is correct
3 Execution timed out 6000 ms 114376 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6000 ms 111388 KB Execution timed out
2 Halted 0 ms 0 KB -