Submission #31227

#	Time	Username	Problem	Language	Result	Execution time	Memory
31227		chonka	Factories (JOI14_factories)	C++98	0 / 100	6000 ms	107536 KiB

factories

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

#define MAXN 500007

int n ;
vector < pair < int , int > > v[ MAXN ] ;
long long dist[ MAXN ] ;

int subtree[ MAXN ] ;

int lvl[ MAXN ] ;
int heavy[ MAXN ] ;
int root[ MAXN ] ;
int pos_in_tree[ MAXN ] ;
int lst[ MAXN ] ;

int rev[ MAXN ] ;

long long inf ;

class Tree {
    public :
    long long tr[ 3 * MAXN ] ;
    long long u[ 3 * MAXN ] ;
    long long lazy[ 3 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        lazy[ where ] = 0 ;
        u[ where ] = inf ;
        if ( IL == IR ) {
            tr[ where ] = -2 * dist[ rev[ IL ] ] ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
        tr[ where ] = min ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
    }
    void push_lazy ( int where , int IL , int IR ) {
        if ( lazy[ where ] == 0 ) { return ; }
        if ( lazy[ where ] > 0 ) {
            u[ where ] = min ( u[ where ] , tr[ where ] + lazy[ where ] ) ;
            if ( IL != IR ) {
                if ( lazy[ 2 * where ] < 0 ) { lazy[ 2 * where ] = 0 ; }
                if ( lazy[ 2 * where + 1 ] < 0 ) { lazy[ 2 * where + 1 ] = 0 ; }
                if ( lazy[ 2 * where ] == 0 ) { lazy[ 2 * where ] = lazy[ where ] ; }
                if ( lazy[ 2 * where + 1 ] == 0 ) { lazy[ 2 * where + 1 ] = lazy[ where ] ; }
                lazy[ 2 * where ] = lazy[ where ] ;
                lazy[ 2 * where + 1 ] = lazy[ where ] ;
            }
            lazy[ where ] = 0 ;
        }
        else {
            u[ where ] = inf ;
            if ( IL != IR ) {
                lazy[ 2 * where ] = -1 ;
                lazy[ 2 * where + 1 ] = -1 ;
            }
            lazy[ where ] = 0 ;
        }
    }
    void update ( int where , int IL , int IR , int CURL , int CURR , long long val ) {
        push_lazy ( where , IL , IR ) ;
        if ( IR < CURL || CURR < IL ) { return ; }
        if ( CURL <= IL && IR <= CURR ) {
            lazy[ where ] = val ;
            if ( val < 0 ) { lazy[ where ] = -1 ; }
            push_lazy ( where , IL , IR ) ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        update ( 2 * where , IL , mid , CURL , CURR , val ) ;
        update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , val ) ;
        u[ where ] = min ( u[ 2 * where ] , u[ 2 * where + 1 ] ) ;
    }
    long long query ( int where , int IL , int IR , int CURL , int CURR ) {
        push_lazy ( where , IL , IR ) ;
        if ( IR < CURL || CURR < IL ) { return inf ; }
        if ( CURL <= IL && IR <= CURR ) {
            return u[ where ] ;
        }
        int mid = ( IL + IR ) / 2 ;
        return min ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
    }
};

Tree w ;

void dfs ( int vertex , int prv ) {
    printf ( "dist[ %d ] = %lld\n" , vertex , dist[ vertex ] ) ;
    int i ;
    int sz = v[ vertex ].size ( ) ;
    subtree[ vertex ] = 1 ;
    int mx , id ;
    mx = id = 0 ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ].first == prv ) { continue ; }
        lst[ v[ vertex ][ i ].first ] = vertex ;
        lvl[ v[ vertex ][ i ].first ] = lvl[ vertex ] + 1 ;
        dist[ v[ vertex ][ i ].first ] = dist[ vertex ] + v[ vertex ][ i ].second ;
        dfs ( v[ vertex ][ i ].first , vertex ) ;
        subtree[ vertex ] += subtree[ v[ vertex ][ i ].first ] ;
        if ( subtree[ v[ vertex ][ i ].first ] > mx ) {
            mx = subtree[ v[ vertex ][ i ].first ] ;
            id = v[ vertex ][ i ].first ;
        }
    }
    heavy[ vertex ] = id ;
}

void decompose ( int vertex , long long val ) {
    while ( vertex != 0 ) {
        int st = root[ vertex ] ;
        w.update ( 1 , 1 , n , pos_in_tree[ st ] , pos_in_tree[ vertex ] , val ) ;
        vertex = lst[ st ] ;
    }
}

long long calc ( int vertex ) {
    long long ret = inf ;
    long long add = dist[ vertex ] ;
    while ( vertex != 0 ) {
        int st = root[ vertex ] ;
        ret = min ( ret , w.query ( 1 , 1 , n , pos_in_tree[ st ] , pos_in_tree[ vertex ] ) ) ;
        vertex = lst[ st ] ;
    }
    ret += add ;
    return ret ;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N ;
    int i , j ;
    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 ] ) ) ;
    }
    dfs ( 1 , -1 ) ;
    int id = 0 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        if ( i == 1 || heavy[ lst[ i ] ] != i ) {
            j = i ;
            while ( j != 0 ) {
                root[ j ] = i ;
                id ++ ;
                pos_in_tree[ j ] = id ;
                rev[ id ] = j ;
                j = heavy[ j ] ;
            }
        }
    }
    inf = 1 ;
    for ( i = 1 ; i <= 16 ; i ++ ) {
        inf *= 10 ;
    }
    w.init ( 1 , 1 , n ) ;
}

long long Query(int S, int X[], int T, int Y[]) {
    int i ;
    for ( i = 0 ; i < S ; i ++ ) {
        X[ i ] ++ ;
        decompose ( X[ i ] , dist[ X[ i ] ] ) ;
    }
    long long ret = inf ;
    for ( i = 0 ; i < T ; i ++ ) {
        Y[ i ] ++ ;
        ret = min ( ret , calc ( Y[ i ] ) ) ;
    }
    for ( i = 0 ; i < S ; i ++ ) {
        decompose ( X[ i ] , -dist[ X[ i ] ] ) ;
    }
    return ret ;
}

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