Submission #629692

#	Time	Username	Problem	Language	Result	Execution time	Memory
629692		chonka	Toll (BOI17_toll)	C++17	100 / 100	78 ms	26220 KiB

toll

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 5e4 + 7 ;
const int inf = 1e9 ;

int k , n , m , q ;


struct node {
    int len ;
    int dp[ 5 ][ 5 ] ;
    node ( ) {
        len = 0 ;
        for ( int i = 0 ; i < k ; ++ i ) {
            for ( int j = 0 ; j < k ; ++ j ) {
                dp[ i ][ j ] = inf ;
            }
        }
    }
};
node mv[ MAXN ] ;

node unite ( node p1 , node p2 ) {
    if ( p1.len == 0 ) { return p2 ; }
    if ( p2.len == 0 ) { return p1 ; }
    node ret = node ( ) ;
    ret.len = p1.len + p2.len ;
    for ( int i = 0 ; i < k ; ++ i ) {
        for ( int j = 0 ; j < k ; ++ j ) {
            for ( int t = 0 ; t < k ; ++ t ) {
                ret.dp[ i ][ t ] = min ( ret.dp[ i ][ t ] , p1.dp[ i ][ j ] + p2.dp[ j ][ t ] ) ;
            }
        }
    }
    return ret ;
}

class Tree {
public :
    node tr[ 4 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        if ( IL == IR ) {
            tr[ where ] = mv[ IL ] ;
            tr[ where ].len = 1 ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
        tr[ where ] = unite ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
    }
    node query ( int where , int IL , int IR , int CURL , int CURR ) {
        if ( IL > IR || CURL > CURR ) { return node ( ) ; }
        if ( IR < CURL || CURR < IL ) { return node ( ) ; }
        if ( CURL <= IL && IR <= CURR ) { return tr[ where ] ; }
        int mid = ( IL + IR ) / 2 ;
        return unite ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
    }
};

Tree w ;

void solve ( ) {
    cin >> k >> n >> m >> q ;
    for ( int i = 0 ; i <= n ; ++ i ) {
        mv[ i ] = node ( ) ;
    }
    for ( int i = 1 , x , y , c ; i <= m ; ++ i ) {
        cin >> x >> y >> c ;
        int wh = ( x / k ) ;
        x %= k , y %= k ;
        mv[ wh + 1 ].dp[ x ][ y ] = min ( mv[ wh + 1 ].dp[ x ][ y ] , c ) ;
    }
    int mx = ( n - 1 ) / k + 1 ;
    w.init ( 1 , 1 , mx ) ;
    while ( q -- ) {
        int x , y ; cin >> x >> y ;
        if ( ( x / k ) >= ( y / k ) ) {
            cout << "-1\n" ;
            continue ;
        }
        node aux = w.query ( 1 , 1 , mx , ( x / k ) + 1 , ( y / k ) ) ;
        x %= k , y %= k ;
        if ( aux.dp[ x ][ y ] == inf ) { cout << "-1\n" ; }
        else { cout << aux.dp[ x ][ y ] << "\n" ; }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44