oj.uz

Submission #31409

# Submission time Handle Problem Language Result Execution time Memory
31409 2017-08-21T10:50:20 Z chonka Factories (JOI14_factories) C++
100 / 100
 4943 ms 221740 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 ][ 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 172724 KB Output is correct
2 Correct 489 ms 172988 KB Output is correct
3 Correct 416 ms 172988 KB Output is correct
4 Correct 439 ms 172988 KB Output is correct
5 Correct 443 ms 173076 KB Output is correct
6 Correct 323 ms 173024 KB Output is correct
7 Correct 469 ms 172988 KB Output is correct
8 Correct 503 ms 172988 KB Output is correct
9 Correct 546 ms 173080 KB Output is correct
10 Correct 356 ms 173024 KB Output is correct
11 Correct 479 ms 172988 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 172724 KB Output is correct
2 Correct 2129 ms 191468 KB Output is correct
3 Correct 2719 ms 195360 KB Output is correct
4 Correct 1219 ms 192436 KB Output is correct
5 Correct 4389 ms 221740 KB Output is correct
6 Correct 3463 ms 194828 KB Output is correct
7 Correct 1109 ms 177136 KB Output is correct
8 Correct 573 ms 176956 KB Output is correct
9 Correct 1419 ms 179832 KB Output is correct
10 Correct 999 ms 177016 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3016 ms 191468 KB Output is correct
2 Correct 2316 ms 191468 KB Output is correct
3 Correct 3943 ms 194136 KB Output is correct
4 Correct 3469 ms 194856 KB Output is correct
5 Correct 4073 ms 194680 KB Output is correct
6 Correct 4943 ms 214512 KB Output is correct
7 Correct 1376 ms 192436 KB Output is correct
8 Correct 4243 ms 194224 KB Output is correct
9 Correct 3599 ms 193560 KB Output is correct
10 Correct 3319 ms 194272 KB Output is correct
11 Correct 1413 ms 180428 KB Output is correct
12 Correct 643 ms 176956 KB Output is correct
13 Correct 966 ms 176420 KB Output is correct
14 Correct 996 ms 176420 KB Output is correct
15 Correct 1089 ms 177020 KB Output is correct
16 Correct 1123 ms 177004 KB Output is correct