oj.uz

Submission #1092902

# Submission time Handle Problem Language Result Execution time Memory
1092902 2024-09-25T10:34:10 Z juicy Toll (BOI17_toll) C++17
7 / 100
 192 ms 102992 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 102484 KB Output is correct
2 Correct 49 ms 99416 KB Output is correct
3 Correct 47 ms 99284 KB Output is correct
4 Correct 48 ms 99352 KB Output is correct
5 Correct 42 ms 99408 KB Output is correct
6 Correct 41 ms 99284 KB Output is correct
7 Correct 43 ms 99408 KB Output is correct
8 Correct 75 ms 102344 KB Output is correct
9 Correct 63 ms 102048 KB Output is correct
10 Correct 52 ms 99812 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 99420 KB Output is correct
2 Incorrect 41 ms 99432 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 99420 KB Output is correct
2 Incorrect 41 ms 99432 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 102484 KB Output is correct
2 Correct 49 ms 99416 KB Output is correct
3 Correct 47 ms 99284 KB Output is correct
4 Correct 48 ms 99352 KB Output is correct
5 Correct 42 ms 99408 KB Output is correct
6 Correct 41 ms 99284 KB Output is correct
7 Correct 43 ms 99408 KB Output is correct
8 Correct 75 ms 102344 KB Output is correct
9 Correct 63 ms 102048 KB Output is correct
10 Correct 52 ms 99812 KB Output is correct
11 Incorrect 165 ms 102992 KB Output isn't correct
12 Halted 0 ms 0 KB -