oj.uz

Submission #756304

# Submission time Handle Problem Language Result Execution time Memory
756304 2023-06-11T12:52:20 Z Shreyan_Paliwal Toll (BOI17_toll) C++17
7 / 100
 134 ms 166800 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 50000;
const int maxo = 10000;
const int maxk = 5;
const int logn = 17;
const int INF = 1e15;

int k, n, m, o;
int dp[maxn][logn][maxk][maxk];
int ans[maxk][maxk], ans2[maxk][maxk];

inline void comb(int a2[maxk][maxk], int a[maxk][maxk], int m[maxk][maxk]) {
    for (int i = 0; i < k; i++)
        for (int j = 0; j < k; j++)
            for (int l = 0; l < k; l++) 
                a2[i][l] = min(a2[i][l], a[i][j] + m[j][l]);
}

// signed main() {
//     cin.tie(nullptr) -> ios::sync_with_stdio(false);
//     freopen("main.in", "r", stdin);

//     fill(dp[0][0][0], dp[0][0][0] + maxn*logn*maxk*maxk, INF);

//     cin >> k >> n >> m >> o;
//     for (int i = 0; i < m; i++) {
//         int a, b, t; cin >> a >> b >> t;
//         dp[a/k][0][a%k][b%k] = t;
//     }

//     // set up binary lifting

//     for (int i = 1; i < logn; i++) { // for each power of 2 jump
//         for (int j = 0; j + (1 << i) <= (n-k+1)/k; j++) { // do all j where j+(power of 2) is still an actual section
//             comb(dp[j][i], dp[j][i-1], dp[j+(1<<(i-1))][i-1]);
//         }
//     }

//     for (int i = 0; i < o; i++) {
//         int a, b; cin >> a >> b;
//         int A = a/k, B = b/k;
//         fill(ans[0], ans[0] + maxk*maxk, INF);
//         ans[a%k][a%k] = 0;
//         for (int j = logn-1; j >= 0; j--)
//             if (((B-A)>>j) & 1) {
//                 fill(ans2[0], ans2[0] + maxk*maxk, INF);
//                 comb(ans2, ans, dp[A][j]);
//                 A += (1<<j);
//                 for (int c = 0; c < k; c++)
//                     for (int d = 0; d < k; d++)
//                         ans[c][d] = ans2[c][d];
//             }
//         cout << (ans[a%k][b%k] == INF ? -1 : ans[a%k][b%k]) << endl;
//     }

//     return 0;
// }

signed main() {
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    // freopen("main.in", "r", stdin);

	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 i = 1; i < logn; i++) { // for each power of 2 jump
        for (int j = 0; j + (1 << i) <= (n-k+1)/k; j++) { // do all j where j+(power of 2) is still an actual section
            comb(dp[j][i], dp[j][i-1], dp[j+(1<<(i-1))][i-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;
		for (int curr = a / k, dest = b / k, i = 16; ~i; i--) {
			if (curr + (1 << i) <= dest) {
				memset(ans2, 0x3f, sizeof ans2);
				comb(ans2, ans, dp[curr][i]);
				memcpy(ans, ans2, sizeof ans);
				curr += (1 << i);
			}
		}
		cout << (ans[a % k][b % k] == 0x3f3f3f3f3f3f3f3f ? -1 : ans[a % k][b % k])
		     << '\n';
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 166636 KB Output is correct
2 Correct 66 ms 166620 KB Output is correct
3 Correct 70 ms 166552 KB Output is correct
4 Correct 65 ms 166604 KB Output is correct
5 Correct 63 ms 166604 KB Output is correct
6 Correct 65 ms 166584 KB Output is correct
7 Correct 79 ms 166532 KB Output is correct
8 Correct 106 ms 166732 KB Output is correct
9 Correct 101 ms 166556 KB Output is correct
10 Correct 103 ms 166800 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 166696 KB Output is correct
2 Correct 63 ms 166592 KB Output is correct
3 Correct 69 ms 166556 KB Output is correct
4 Correct 63 ms 166560 KB Output is correct
5 Incorrect 78 ms 166524 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 166568 KB Output is correct
2 Correct 62 ms 166632 KB Output is correct
3 Incorrect 70 ms 166604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 166568 KB Output is correct
2 Correct 62 ms 166632 KB Output is correct
3 Incorrect 70 ms 166604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 166636 KB Output is correct
2 Correct 66 ms 166620 KB Output is correct
3 Correct 70 ms 166552 KB Output is correct
4 Correct 65 ms 166604 KB Output is correct
5 Correct 63 ms 166604 KB Output is correct
6 Correct 65 ms 166584 KB Output is correct
7 Correct 79 ms 166532 KB Output is correct
8 Correct 106 ms 166732 KB Output is correct
9 Correct 101 ms 166556 KB Output is correct
10 Correct 103 ms 166800 KB Output is correct
11 Correct 134 ms 166696 KB Output is correct
12 Correct 63 ms 166592 KB Output is correct
13 Correct 69 ms 166556 KB Output is correct
14 Correct 63 ms 166560 KB Output is correct
15 Incorrect 78 ms 166524 KB Output isn't correct
16 Halted 0 ms 0 KB -