oj.uz

Submission #756292

# Submission time Handle Problem Language Result Execution time Memory
756292 2023-06-11T12:29:02 Z Shreyan_Paliwal Toll (BOI17_toll) C++17
7 / 100
 160 ms 94788 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

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
            for (int a = 0; a < k; a++) {
                for (int b = 0; b < k; b++) {
                    for (int c = 0; c < k; c++) {
                        dp[j][i][a][c] = min(
                            dp[j][i][a][c],
                            dp[j][i-1][a][b]+
                            dp[j+(1<<(i-1))][i-1][b][c]
                        );
                    }
                }
            }
            // cout << j << ' ' << j+(1<<i) << endl;
            // for (int a = 0; a < 5; a++) {
            //     for (int b = 0; b < 5; b++) {
            //         cout << dp[j][i][a][b] << ' ';
            //     }
            //     cout << endl;
            // }
        }
    }

    int ans[k][k], ans2[k][k];
    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] + k*k, 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) {
                // cout << B << ' ' << A << ' ' << j << endl;
                // make jump of size j
                fill(ans2[0], ans2[0] + k*k, INF);
                for (int c = 0; c < k; c++)
                    for (int d = 0; d < k; d++)
                        for (int e = 0; e < k; e++) {
                            // if (a%k == c && a%k == d && b%k == e) cout << A << ' ' << j << ' ' << d << ' ' << e << ' ' << ans[c][d] << ' ' << dp[A][j][d][e] << endl;
                            ans2[c][e] = min(
                                ans2[c][e], 
                                ans[c][d] + dp[A][j][d][e]
                            );
                        }
                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 116 ms 94244 KB Output is correct
2 Correct 48 ms 93236 KB Output is correct
3 Correct 42 ms 93132 KB Output is correct
4 Correct 43 ms 93240 KB Output is correct
5 Correct 48 ms 93224 KB Output is correct
6 Correct 57 ms 93212 KB Output is correct
7 Correct 45 ms 93224 KB Output is correct
8 Correct 122 ms 94120 KB Output is correct
9 Correct 114 ms 94036 KB Output is correct
10 Correct 78 ms 93284 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 94788 KB Output is correct
2 Correct 47 ms 93132 KB Output is correct
3 Correct 45 ms 93208 KB Output is correct
4 Correct 43 ms 93252 KB Output is correct
5 Incorrect 50 ms 93204 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 93196 KB Output is correct
2 Correct 44 ms 93200 KB Output is correct
3 Incorrect 41 ms 93252 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 93196 KB Output is correct
2 Correct 44 ms 93200 KB Output is correct
3 Incorrect 41 ms 93252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 94244 KB Output is correct
2 Correct 48 ms 93236 KB Output is correct
3 Correct 42 ms 93132 KB Output is correct
4 Correct 43 ms 93240 KB Output is correct
5 Correct 48 ms 93224 KB Output is correct
6 Correct 57 ms 93212 KB Output is correct
7 Correct 45 ms 93224 KB Output is correct
8 Correct 122 ms 94120 KB Output is correct
9 Correct 114 ms 94036 KB Output is correct
10 Correct 78 ms 93284 KB Output is correct
11 Correct 160 ms 94788 KB Output is correct
12 Correct 47 ms 93132 KB Output is correct
13 Correct 45 ms 93208 KB Output is correct
14 Correct 43 ms 93252 KB Output is correct
15 Incorrect 50 ms 93204 KB Output isn't correct
16 Halted 0 ms 0 KB -