oj.uz

Submission #697193

# Submission time Handle Problem Language Result Execution time Memory
697193 2023-02-08T18:54:28 Z _martynas Toll (BOI17_toll) C++11
0 / 100
 92 ms 17564 KB 
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct Edge {
    int v, w;
};

const int MXN = 5e4+5;
const int INF = 1e9;

int k, n, m, o;
// [a][b][c] = from a move 2^b blocks ahead to position = c (mod k)
int jump[MXN][16][5];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> k >> n >> m >> o;
    for(int a = 0; a < n; a++)
    for(int b = 0; b < 16; b++)
    for(int c = 0; c < 5; c++)
        jump[a][b][c] = INF;
    for(int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        jump[u][0][v%k] = w;
    }

    for(int p = 1; p < 16; p++) {
        int blocks = 1 << p;
        for(int a = 0; a < n; a++) {
            if(a+k*blocks >= n) continue;
            for(int b = 0; b < 5; b++)
                for(int c = 0; c < 5; c++)
                    jump[a][p][c] = min(jump[a][p][c], jump[a][p-1][b]+jump[a+k*(blocks/2)-a%k+b][p-1][c]);
        }
    }

    for(int _ = 0; _ < o; _++) {
        int a, b; cin >> a >> b;
        vi dist(5, INF);
        dist[a%k] = 0;
        for(int p = 15; p >= 0; p--) {
            int blocks = 1 << p;
            if(a+k*blocks >= n) continue;
            while(a+k*blocks-a%k <= b) {
                vi ndist(5, INF);
                for(int i = 0; i < 5; i++) {
                    for(int j = 0; j < 5; j++) {
                        ndist[j] = min(ndist[j], jump[a-a%k+i][p][j]);
                    }
                }
                a = a+k*blocks;
                dist = ndist;
            }
        }
        int d = dist[b%k];
        if(d == INF) cout << "-1\n";
        else cout << d << "\n";
    }
    return 0;
}
/*

*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 16872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 17564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 16872 KB Output isn't correct
2 Halted 0 ms 0 KB -