oj.uz

Submission #756297

# Submission time Handle Problem Language Result Execution time Memory
756297 2023-06-11T12:33:28 Z Shreyan_Paliwal Toll (BOI17_toll) C++17
7 / 100
 214 ms 186416 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 = 19;
const int INF = 1e15;

int k, n, m, o;
pair<int,int> orders[maxo];
int dp[maxn][logn][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() {
    // 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]);
        }
    }

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 186188 KB Output is correct
2 Correct 85 ms 186112 KB Output is correct
3 Correct 82 ms 186104 KB Output is correct
4 Correct 81 ms 186188 KB Output is correct
5 Correct 81 ms 186196 KB Output is correct
6 Correct 85 ms 186096 KB Output is correct
7 Correct 81 ms 186176 KB Output is correct
8 Correct 176 ms 186132 KB Output is correct
9 Correct 156 ms 186416 KB Output is correct
10 Correct 120 ms 186212 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 186180 KB Output is correct
2 Correct 78 ms 186188 KB Output is correct
3 Correct 81 ms 186188 KB Output is correct
4 Correct 87 ms 186172 KB Output is correct
5 Incorrect 82 ms 186212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 186132 KB Output is correct
2 Correct 80 ms 186132 KB Output is correct
3 Incorrect 84 ms 186188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 186132 KB Output is correct
2 Correct 80 ms 186132 KB Output is correct
3 Incorrect 84 ms 186188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 186188 KB Output is correct
2 Correct 85 ms 186112 KB Output is correct
3 Correct 82 ms 186104 KB Output is correct
4 Correct 81 ms 186188 KB Output is correct
5 Correct 81 ms 186196 KB Output is correct
6 Correct 85 ms 186096 KB Output is correct
7 Correct 81 ms 186176 KB Output is correct
8 Correct 176 ms 186132 KB Output is correct
9 Correct 156 ms 186416 KB Output is correct
10 Correct 120 ms 186212 KB Output is correct
11 Correct 214 ms 186180 KB Output is correct
12 Correct 78 ms 186188 KB Output is correct
13 Correct 81 ms 186188 KB Output is correct
14 Correct 87 ms 186172 KB Output is correct
15 Incorrect 82 ms 186212 KB Output isn't correct
16 Halted 0 ms 0 KB -