Submission #1216704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216704		uranium235	Toll (BOI17_toll)	Java	100 / 100	488 ms	108972 KiB

toll

//package ojuz;

import java.io.*;
import java.util.*;

public class toll {
    public static final int inf = 1_000_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] first = reader.readLine().split(" ");
        int k = Integer.parseInt(first[0]), n = Math.floorDiv(Integer.parseInt(first[1]) + k - 1, k) * k, m = Integer.parseInt(first[2]), q = Integer.parseInt(first[3]);

        int log = 32 - Integer.numberOfLeadingZeros(n - 1);
        // for node i, the min cost of toll up to (2 ** i) layers after, ending on node k on that layer
        int[][][] lift = new int[log][n][k];
        for (int[][] arr : lift) for (int[] ar : arr) Arrays.fill(ar, inf);
        for (int i = 0; i < m; i++) {
            String[] edge = reader.readLine().split(" ");
            int a = Integer.parseInt(edge[0]), b = Integer.parseInt(edge[1]), t = Integer.parseInt(edge[2]);
            lift[0][a][b % k] = t;
        }

        for (int i = 1; i < log; i++) {
            for (int j = 0; j < n; j++) {
                int next = (j / k) * k + (k << (i - 1));
                if (next >= n) continue;
                for (int l = 0; l < k; l++) {
                    for (int o = 0; o < k; o++) {
                        lift[i][j][l] = Math.min(lift[i][j][l], lift[i - 1][j][o] + lift[i - 1][next + o][l]);
                    }
                }
            }
        }

        int[] best = new int[k];
        int[] aux = new int[k];
        for (int i = 0; i < q; i++) {
            String[] query = reader.readLine().split(" ");
            int a = Integer.parseInt(query[0]), b = Integer.parseInt(query[1]);
            int dist = (b / k) - (a / k);
            int cur = a / k;
            Arrays.fill(best, inf);
            best[a % k] = 0;
            for (int j = log; j >= 0; j--) {
                if (dist >= (1 << j)) {
                    dist -= 1 << j;
                    Arrays.fill(aux, inf);
                    for (int l = 0; l < k; l++) {
                        for (int o = 0; o < k; o++) {
                            aux[l] = Math.min(aux[l], best[o] + lift[j][cur * k + o][l]);
                        }
                    }
                    cur += 1 << j;

                    int[] temp = best;
                    best = aux;
                    aux = temp;
                }
            }

            writer.write(best[b % k] == inf ? "-1" : String.valueOf(best[b % k]));
            writer.newLine();
        }

        writer.flush();
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44