oj.uz

Submission #756296

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

const int maxn = 50000;
const int maxo = 10000;
const int maxk = 5;
const int logn = 19;
const int INF = 1e9;

int k, n, m, o;
pair<int,int> orders[maxo];
int dp[maxn][logn][maxk][maxk]; // from k*maxn+maxk1 --> k*(maxn+2^logn) + maxk2

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]);
}

int main() {
    // 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;
    }

    // for (int i = 0; i <= 1; i++) {
    //     for (int a = 0; a < 5; a++) {
    //         for (int b = 0; b < 5; b++) {
    //             cout << dp[i][0][a][b] << ' ';
    //         }
    //         cout << endl;
    //     }
    // }

    // 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]);
        }
    }

    int ans[maxk][maxk], ans2[maxk][maxk];
    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);
        for (int j = 0; j < k; j++) ans[j][j] = 0;
        // ans[a%k][a%k] = 0; // because we are starting at a%k, and only care about paths from it
        // a->b where a =/= b doesn't make sense since we haven't made jumps, and rest we aren't starting at it
        for (int j = logn-1; j >= 0; j--)
            if (((B-A)>>j) & 1) {
                // make jump of size j
                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;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 93260 KB Output is correct
2 Correct 50 ms 93316 KB Output is correct
3 Correct 48 ms 93164 KB Output is correct
4 Correct 43 ms 93152 KB Output is correct
5 Correct 55 ms 93120 KB Output is correct
6 Correct 46 ms 93208 KB Output is correct
7 Correct 47 ms 93176 KB Output is correct
8 Correct 140 ms 93232 KB Output is correct
9 Correct 123 ms 93168 KB Output is correct
10 Correct 101 ms 93192 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 93236 KB Output is correct
2 Correct 45 ms 93200 KB Output is correct
3 Correct 46 ms 93232 KB Output is correct
4 Correct 43 ms 93140 KB Output is correct
5 Incorrect 43 ms 93156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 93212 KB Output is correct
2 Correct 48 ms 93180 KB Output is correct
3 Incorrect 43 ms 93260 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 93212 KB Output is correct
2 Correct 48 ms 93180 KB Output is correct
3 Incorrect 43 ms 93260 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 93260 KB Output is correct
2 Correct 50 ms 93316 KB Output is correct
3 Correct 48 ms 93164 KB Output is correct
4 Correct 43 ms 93152 KB Output is correct
5 Correct 55 ms 93120 KB Output is correct
6 Correct 46 ms 93208 KB Output is correct
7 Correct 47 ms 93176 KB Output is correct
8 Correct 140 ms 93232 KB Output is correct
9 Correct 123 ms 93168 KB Output is correct
10 Correct 101 ms 93192 KB Output is correct
11 Correct 179 ms 93236 KB Output is correct
12 Correct 45 ms 93200 KB Output is correct
13 Correct 46 ms 93232 KB Output is correct
14 Correct 43 ms 93140 KB Output is correct
15 Incorrect 43 ms 93156 KB Output isn't correct
16 Halted 0 ms 0 KB -