Submission #1092902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092902		juicy	Toll (BOI17_toll)	C++17	7 / 100	192 ms	102992 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5e4, B = 100, inf = 1e9;

int k, n, m, o;
int d[N][500], blk[N], lt[500], rt[500], nxt[N];
vector<array<int, 2>> g[N];

int qry(vector<array<int, 2>> a, int b) {
  int id = blk[a[0][0]];
  if (id == blk[b]) {
    int res = inf;
    b -= lt[id];
    for (auto [u, c] : a) {
      if (d[u][b] < inf) {
        res = min(res, c + d[u][b]);
      }
    }
    return res == inf ? -1 : res;
  }
  fill(nxt + rt[id] + 1, nxt + rt[id] + 1 + k, inf);
  for (int i = rt[id] - k + 1; i <= rt[id]; ++i) {
    int k = i - lt[id], cur = inf;
    for (auto [u, c] : a) {
      if (d[u][k] < inf) {
        cur = min(cur, c + d[u][k]);
      }
    }
    if (cur != inf) {
      for (auto [v, c] : g[i]) {
        nxt[v] = min(nxt[v], cur + c);
      }
    }
  }
  vector<array<int, 2>> nw;
  for (int i = rt[id] + 1; i <= rt[id] + k; ++i) {
    if (nxt[i] != inf) {
      nw.push_back({i, nxt[i]});
    }
  }
  return !nw.size() ? -1 : qry(nw, b);
}

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

  cin >> k >> n >> m >> o;
  for (int i = 0; i < n; ++i) {
    blk[i] = i / k / B;
    rt[blk[i]] = i;
  }
  for (int i = n - 1; ~i; --i) {
    lt[blk[i]] = i;
  }
  while (m--) {
    int a, b, c; cin >> a >> b >> c;
    g[a].push_back({b, c});
  }
  memset(d, 0x3f, sizeof(d));
  for (int i = 0; i < n; ++i) {
    int id = blk[i];
    d[i][i - lt[id]] = 0;
    for (int j = i; blk[j] == id; ++j) {
      if (d[i][j - lt[id]] < inf) {
        for (auto [k, w] : g[j]) {
          if (k <= rt[id]) {
            d[i][k - lt[id]] = d[i][j - lt[id]] + w;
          }
        }
      }
    }
  }
  while (o--) {
    int a, b; cin >> a >> b;
    cout << qry({{a, 0}}, b) << "\n";
  }
  return 0;
}

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