# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
629692 |
2022-08-14T22:21:02 Z |
chonka |
Toll (BOI17_toll) |
C++17 |
|
78 ms |
26220 KB |
#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 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
26064 KB |
Output is correct |
2 |
Correct |
10 ms |
25684 KB |
Output is correct |
3 |
Correct |
11 ms |
25748 KB |
Output is correct |
4 |
Correct |
10 ms |
25772 KB |
Output is correct |
5 |
Correct |
12 ms |
25780 KB |
Output is correct |
6 |
Correct |
11 ms |
25684 KB |
Output is correct |
7 |
Correct |
12 ms |
25696 KB |
Output is correct |
8 |
Correct |
36 ms |
26024 KB |
Output is correct |
9 |
Correct |
37 ms |
26020 KB |
Output is correct |
10 |
Correct |
24 ms |
25888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
26052 KB |
Output is correct |
2 |
Correct |
12 ms |
25688 KB |
Output is correct |
3 |
Correct |
10 ms |
25692 KB |
Output is correct |
4 |
Correct |
10 ms |
25732 KB |
Output is correct |
5 |
Correct |
10 ms |
25684 KB |
Output is correct |
6 |
Correct |
10 ms |
25728 KB |
Output is correct |
7 |
Correct |
16 ms |
25784 KB |
Output is correct |
8 |
Correct |
15 ms |
25812 KB |
Output is correct |
9 |
Correct |
36 ms |
26148 KB |
Output is correct |
10 |
Correct |
52 ms |
26204 KB |
Output is correct |
11 |
Correct |
46 ms |
26220 KB |
Output is correct |
12 |
Correct |
40 ms |
26152 KB |
Output is correct |
13 |
Correct |
49 ms |
26144 KB |
Output is correct |
14 |
Correct |
38 ms |
26152 KB |
Output is correct |
15 |
Correct |
33 ms |
26156 KB |
Output is correct |
16 |
Correct |
33 ms |
26156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
25692 KB |
Output is correct |
2 |
Correct |
11 ms |
25768 KB |
Output is correct |
3 |
Correct |
10 ms |
25764 KB |
Output is correct |
4 |
Correct |
10 ms |
25684 KB |
Output is correct |
5 |
Correct |
12 ms |
25684 KB |
Output is correct |
6 |
Correct |
10 ms |
25684 KB |
Output is correct |
7 |
Correct |
11 ms |
25848 KB |
Output is correct |
8 |
Correct |
11 ms |
25708 KB |
Output is correct |
9 |
Correct |
12 ms |
25812 KB |
Output is correct |
10 |
Correct |
27 ms |
26096 KB |
Output is correct |
11 |
Correct |
36 ms |
26052 KB |
Output is correct |
12 |
Correct |
47 ms |
26112 KB |
Output is correct |
13 |
Correct |
50 ms |
26132 KB |
Output is correct |
14 |
Correct |
40 ms |
26060 KB |
Output is correct |
15 |
Correct |
32 ms |
26188 KB |
Output is correct |
16 |
Correct |
32 ms |
26096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
25692 KB |
Output is correct |
2 |
Correct |
11 ms |
25768 KB |
Output is correct |
3 |
Correct |
10 ms |
25764 KB |
Output is correct |
4 |
Correct |
10 ms |
25684 KB |
Output is correct |
5 |
Correct |
12 ms |
25684 KB |
Output is correct |
6 |
Correct |
10 ms |
25684 KB |
Output is correct |
7 |
Correct |
11 ms |
25848 KB |
Output is correct |
8 |
Correct |
11 ms |
25708 KB |
Output is correct |
9 |
Correct |
12 ms |
25812 KB |
Output is correct |
10 |
Correct |
27 ms |
26096 KB |
Output is correct |
11 |
Correct |
36 ms |
26052 KB |
Output is correct |
12 |
Correct |
47 ms |
26112 KB |
Output is correct |
13 |
Correct |
50 ms |
26132 KB |
Output is correct |
14 |
Correct |
40 ms |
26060 KB |
Output is correct |
15 |
Correct |
32 ms |
26188 KB |
Output is correct |
16 |
Correct |
32 ms |
26096 KB |
Output is correct |
17 |
Correct |
39 ms |
26144 KB |
Output is correct |
18 |
Correct |
11 ms |
25764 KB |
Output is correct |
19 |
Correct |
10 ms |
25684 KB |
Output is correct |
20 |
Correct |
10 ms |
25684 KB |
Output is correct |
21 |
Correct |
10 ms |
25648 KB |
Output is correct |
22 |
Correct |
10 ms |
25684 KB |
Output is correct |
23 |
Correct |
13 ms |
25704 KB |
Output is correct |
24 |
Correct |
14 ms |
25812 KB |
Output is correct |
25 |
Correct |
15 ms |
25788 KB |
Output is correct |
26 |
Correct |
16 ms |
25776 KB |
Output is correct |
27 |
Correct |
31 ms |
26128 KB |
Output is correct |
28 |
Correct |
51 ms |
26040 KB |
Output is correct |
29 |
Correct |
52 ms |
26060 KB |
Output is correct |
30 |
Correct |
43 ms |
26128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
26064 KB |
Output is correct |
2 |
Correct |
10 ms |
25684 KB |
Output is correct |
3 |
Correct |
11 ms |
25748 KB |
Output is correct |
4 |
Correct |
10 ms |
25772 KB |
Output is correct |
5 |
Correct |
12 ms |
25780 KB |
Output is correct |
6 |
Correct |
11 ms |
25684 KB |
Output is correct |
7 |
Correct |
12 ms |
25696 KB |
Output is correct |
8 |
Correct |
36 ms |
26024 KB |
Output is correct |
9 |
Correct |
37 ms |
26020 KB |
Output is correct |
10 |
Correct |
24 ms |
25888 KB |
Output is correct |
11 |
Correct |
42 ms |
26052 KB |
Output is correct |
12 |
Correct |
12 ms |
25688 KB |
Output is correct |
13 |
Correct |
10 ms |
25692 KB |
Output is correct |
14 |
Correct |
10 ms |
25732 KB |
Output is correct |
15 |
Correct |
10 ms |
25684 KB |
Output is correct |
16 |
Correct |
10 ms |
25728 KB |
Output is correct |
17 |
Correct |
16 ms |
25784 KB |
Output is correct |
18 |
Correct |
15 ms |
25812 KB |
Output is correct |
19 |
Correct |
36 ms |
26148 KB |
Output is correct |
20 |
Correct |
52 ms |
26204 KB |
Output is correct |
21 |
Correct |
46 ms |
26220 KB |
Output is correct |
22 |
Correct |
40 ms |
26152 KB |
Output is correct |
23 |
Correct |
49 ms |
26144 KB |
Output is correct |
24 |
Correct |
38 ms |
26152 KB |
Output is correct |
25 |
Correct |
33 ms |
26156 KB |
Output is correct |
26 |
Correct |
33 ms |
26156 KB |
Output is correct |
27 |
Correct |
10 ms |
25692 KB |
Output is correct |
28 |
Correct |
11 ms |
25768 KB |
Output is correct |
29 |
Correct |
10 ms |
25764 KB |
Output is correct |
30 |
Correct |
10 ms |
25684 KB |
Output is correct |
31 |
Correct |
12 ms |
25684 KB |
Output is correct |
32 |
Correct |
10 ms |
25684 KB |
Output is correct |
33 |
Correct |
11 ms |
25848 KB |
Output is correct |
34 |
Correct |
11 ms |
25708 KB |
Output is correct |
35 |
Correct |
12 ms |
25812 KB |
Output is correct |
36 |
Correct |
27 ms |
26096 KB |
Output is correct |
37 |
Correct |
36 ms |
26052 KB |
Output is correct |
38 |
Correct |
47 ms |
26112 KB |
Output is correct |
39 |
Correct |
50 ms |
26132 KB |
Output is correct |
40 |
Correct |
40 ms |
26060 KB |
Output is correct |
41 |
Correct |
32 ms |
26188 KB |
Output is correct |
42 |
Correct |
32 ms |
26096 KB |
Output is correct |
43 |
Correct |
39 ms |
26144 KB |
Output is correct |
44 |
Correct |
11 ms |
25764 KB |
Output is correct |
45 |
Correct |
10 ms |
25684 KB |
Output is correct |
46 |
Correct |
10 ms |
25684 KB |
Output is correct |
47 |
Correct |
10 ms |
25648 KB |
Output is correct |
48 |
Correct |
10 ms |
25684 KB |
Output is correct |
49 |
Correct |
13 ms |
25704 KB |
Output is correct |
50 |
Correct |
14 ms |
25812 KB |
Output is correct |
51 |
Correct |
15 ms |
25788 KB |
Output is correct |
52 |
Correct |
16 ms |
25776 KB |
Output is correct |
53 |
Correct |
31 ms |
26128 KB |
Output is correct |
54 |
Correct |
51 ms |
26040 KB |
Output is correct |
55 |
Correct |
52 ms |
26060 KB |
Output is correct |
56 |
Correct |
43 ms |
26128 KB |
Output is correct |
57 |
Correct |
78 ms |
26160 KB |
Output is correct |
58 |
Correct |
38 ms |
26160 KB |
Output is correct |
59 |
Correct |
46 ms |
26128 KB |
Output is correct |