Submission #404770

#	Time	Username	Problem	Language	Result	Execution time	Memory
404770		rama_pang	Toll (BOI17_toll)	C++17	100 / 100	95 ms	15984 KiB

toll

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int K, N, M, O;
  cin >> K >> N >> M >> O;
  while (N % K != 0) N += 1;

  const int INF = 1e9;
  vector<array<array<int, 5>, 5>> A(N / K);
  for (int i = 0; i < N / K; i++) {
    for (int x = 0; x < K; x++) {
      for (int y = 0; y < K; y++) {
        A[i][x][y] = INF;
      }
    }
  }

  while (M--) {
    int a, b, t;
    cin >> a >> b >> t;
    assert(a / K + 1 == b / K);
    A[a / K][a % K][b % K] = min(A[a / K][a % K][b % K], t);
  }

  vector<array<array<int, 5>, 5>> tree(N / K * 2);

  const auto Merge = [&](array<array<int, 5>, 5> p, array<array<int, 5>, 5> q) {
    array<array<int, 5>, 5> res;
    for (int i = 0; i < K; i++) {
      for (int j = 0; j < K; j++) {
        res[i][j] = INF;
        for (int k = 0; k < K; k++) {
          res[i][j] = min(res[i][j], p[i][k] + q[k][j]);
        }
      }
    }
    return res;
  };

  for (int i = 0; i < N / K; i++) {
    tree[i + N / K] = A[i];
  }
  for (int i = N / K - 1; i > 0; i--) {
    tree[i] = Merge(tree[i * 2], tree[i * 2 + 1]);
  }

  const auto Query = [&](int l, int r) {
    array<array<int, 5>, 5> lft;
    array<array<int, 5>, 5> rgt;
    for (int i = 0; i < K; i++) {
      for (int j = 0; j < K; j++) {
        lft[i][j] = i == j ? 0 : INF;
        rgt[i][j] = i == j ? 0 : INF;
      }
    }
    for (l += N / K, r += N / K; l < r; l /= 2, r /= 2) {
      if (l & 1) lft = Merge(lft, tree[l++]);
      if (r & 1) rgt = Merge(tree[--r], rgt);
    }
    return Merge(lft, rgt);
  };

  while (O--) {
    int a, b;
    cin >> a >> b;
    if (b / K <= a / K) {
      cout << -1 << '\n';
      continue;
    }
    assert(a / K + 1 <= b / K);
    int ans = Query(a / K, b / K)[a % K][b % K];
    if (ans == INF) {
      cout << -1 << '\n';
    } else {
      cout << ans << '\n';
    }
  }
  return 0;
}

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