oj.uz

Submission #437209

# Submission time Handle Problem Language Result Execution time Memory
437209 2021-06-26T04:33:45 Z john256 Toll (BOI17_toll) C++14
100 / 100
 170 ms 86836 KB 
#include <bits/stdc++.h>
using namespace std;

int k, n, m, o;
int dp[50000][17][5][5], ans[5][5], tmp[5][5];

void combine(int target[5][5], int a[5][5], int b[5][5]) {
	for(int x=0; x<k; x++) {
		for(int y=0; y<k; y++) {
			for(int z=0; z<k; z++) {
				target[x][y] = min(target[x][y], a[x][z] + b[z][y]);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> k >> n >> m >> o;
	memset(dp, 0x3f, sizeof dp);
	while(m--) {
		int a, b, t;
		cin >> a >> b >> t;
		dp[a/k][0][a%k][b%k] = t;
	}

	for(int j=1; j<17; j++) {
		for(int i=0; i+(1<<j) < (n+k-1)/k; i++) {
			combine(dp[i][j], dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
		}
	}

	while(o--) {
		int a, b;
		cin >> a >> b;
		memset(ans, 0x3f, sizeof ans);
		
		for(int i=0; i<5; i++) 
			ans[i][i] = 0;
		
		int curr=a/k, dest=b/k;
		for(int i=16; i>=0; i--) {
			if(curr + (1<<i) <= dest) {
				memset(tmp, 0x3f, sizeof tmp);
				combine(tmp, ans, dp[curr][i]);
				memcpy(ans, tmp, sizeof ans);
				curr += (1<<i);
			}
		}
		cout << (ans[a%k][b%k] == 0x3f3f3f3f ? -1 : ans[a%k][b%k]) << '\n';
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 83464 KB Output is correct
2 Correct 40 ms 83480 KB Output is correct
3 Correct 41 ms 83404 KB Output is correct
4 Correct 46 ms 83396 KB Output is correct
5 Correct 39 ms 83404 KB Output is correct
6 Correct 41 ms 83396 KB Output is correct
7 Correct 40 ms 83396 KB Output is correct
8 Correct 112 ms 84420 KB Output is correct
9 Correct 123 ms 84292 KB Output is correct
10 Correct 86 ms 83536 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 83524 KB Output is correct
2 Correct 40 ms 83360 KB Output is correct
3 Correct 38 ms 83456 KB Output is correct
4 Correct 38 ms 83352 KB Output is correct
5 Correct 39 ms 83352 KB Output is correct
6 Correct 39 ms 83448 KB Output is correct
7 Correct 44 ms 83560 KB Output is correct
8 Correct 46 ms 83544 KB Output is correct
9 Correct 97 ms 84292 KB Output is correct
10 Correct 146 ms 85720 KB Output is correct
11 Correct 162 ms 85208 KB Output is correct
12 Correct 118 ms 84724 KB Output is correct
13 Correct 110 ms 85792 KB Output is correct
14 Correct 84 ms 84932 KB Output is correct
15 Correct 109 ms 84596 KB Output is correct
16 Correct 87 ms 84600 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 83396 KB Output is correct
2 Correct 44 ms 83448 KB Output is correct
3 Correct 44 ms 83396 KB Output is correct
4 Correct 39 ms 83380 KB Output is correct
5 Correct 43 ms 83448 KB Output is correct
6 Correct 40 ms 83412 KB Output is correct
7 Correct 42 ms 83428 KB Output is correct
8 Correct 43 ms 83496 KB Output is correct
9 Correct 40 ms 83404 KB Output is correct
10 Correct 94 ms 84240 KB Output is correct
11 Correct 133 ms 84996 KB Output is correct
12 Correct 139 ms 85632 KB Output is correct
13 Correct 132 ms 86004 KB Output is correct
14 Correct 118 ms 85260 KB Output is correct
15 Correct 83 ms 84596 KB Output is correct
16 Correct 78 ms 84640 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 83396 KB Output is correct
2 Correct 44 ms 83448 KB Output is correct
3 Correct 44 ms 83396 KB Output is correct
4 Correct 39 ms 83380 KB Output is correct
5 Correct 43 ms 83448 KB Output is correct
6 Correct 40 ms 83412 KB Output is correct
7 Correct 42 ms 83428 KB Output is correct
8 Correct 43 ms 83496 KB Output is correct
9 Correct 40 ms 83404 KB Output is correct
10 Correct 94 ms 84240 KB Output is correct
11 Correct 133 ms 84996 KB Output is correct
12 Correct 139 ms 85632 KB Output is correct
13 Correct 132 ms 86004 KB Output is correct
14 Correct 118 ms 85260 KB Output is correct
15 Correct 83 ms 84596 KB Output is correct
16 Correct 78 ms 84640 KB Output is correct
17 Correct 121 ms 85116 KB Output is correct
18 Correct 39 ms 83368 KB Output is correct
19 Correct 40 ms 83408 KB Output is correct
20 Correct 40 ms 83384 KB Output is correct
21 Correct 48 ms 83416 KB Output is correct
22 Correct 40 ms 83392 KB Output is correct
23 Correct 47 ms 83392 KB Output is correct
24 Correct 43 ms 83524 KB Output is correct
25 Correct 42 ms 83564 KB Output is correct
26 Correct 43 ms 83524 KB Output is correct
27 Correct 94 ms 84224 KB Output is correct
28 Correct 127 ms 85624 KB Output is correct
29 Correct 149 ms 85912 KB Output is correct
30 Correct 136 ms 85228 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 83464 KB Output is correct
2 Correct 40 ms 83480 KB Output is correct
3 Correct 41 ms 83404 KB Output is correct
4 Correct 46 ms 83396 KB Output is correct
5 Correct 39 ms 83404 KB Output is correct
6 Correct 41 ms 83396 KB Output is correct
7 Correct 40 ms 83396 KB Output is correct
8 Correct 112 ms 84420 KB Output is correct
9 Correct 123 ms 84292 KB Output is correct
10 Correct 86 ms 83536 KB Output is correct
11 Correct 141 ms 83524 KB Output is correct
12 Correct 40 ms 83360 KB Output is correct
13 Correct 38 ms 83456 KB Output is correct
14 Correct 38 ms 83352 KB Output is correct
15 Correct 39 ms 83352 KB Output is correct
16 Correct 39 ms 83448 KB Output is correct
17 Correct 44 ms 83560 KB Output is correct
18 Correct 46 ms 83544 KB Output is correct
19 Correct 97 ms 84292 KB Output is correct
20 Correct 146 ms 85720 KB Output is correct
21 Correct 162 ms 85208 KB Output is correct
22 Correct 118 ms 84724 KB Output is correct
23 Correct 110 ms 85792 KB Output is correct
24 Correct 84 ms 84932 KB Output is correct
25 Correct 109 ms 84596 KB Output is correct
26 Correct 87 ms 84600 KB Output is correct
27 Correct 39 ms 83396 KB Output is correct
28 Correct 44 ms 83448 KB Output is correct
29 Correct 44 ms 83396 KB Output is correct
30 Correct 39 ms 83380 KB Output is correct
31 Correct 43 ms 83448 KB Output is correct
32 Correct 40 ms 83412 KB Output is correct
33 Correct 42 ms 83428 KB Output is correct
34 Correct 43 ms 83496 KB Output is correct
35 Correct 40 ms 83404 KB Output is correct
36 Correct 94 ms 84240 KB Output is correct
37 Correct 133 ms 84996 KB Output is correct
38 Correct 139 ms 85632 KB Output is correct
39 Correct 132 ms 86004 KB Output is correct
40 Correct 118 ms 85260 KB Output is correct
41 Correct 83 ms 84596 KB Output is correct
42 Correct 78 ms 84640 KB Output is correct
43 Correct 121 ms 85116 KB Output is correct
44 Correct 39 ms 83368 KB Output is correct
45 Correct 40 ms 83408 KB Output is correct
46 Correct 40 ms 83384 KB Output is correct
47 Correct 48 ms 83416 KB Output is correct
48 Correct 40 ms 83392 KB Output is correct
49 Correct 47 ms 83392 KB Output is correct
50 Correct 43 ms 83524 KB Output is correct
51 Correct 42 ms 83564 KB Output is correct
52 Correct 43 ms 83524 KB Output is correct
53 Correct 94 ms 84224 KB Output is correct
54 Correct 127 ms 85624 KB Output is correct
55 Correct 149 ms 85912 KB Output is correct
56 Correct 136 ms 85228 KB Output is correct
57 Correct 170 ms 86836 KB Output is correct
58 Correct 109 ms 84296 KB Output is correct
59 Correct 148 ms 85252 KB Output is correct