Submission #697195

#	Time	Username	Problem	Language	Result	Execution time	Memory
697195		_martynas	Toll (BOI17_toll)	C++11	100 / 100	116 ms	17796 KiB

toll

#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-a%k >= 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-a%k >= 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], dist[i]+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: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44