Submission #1092906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092906		juicy	Toll (BOI17_toll)	C++17	100 / 100	66 ms	25476 KiB

toll

#include <bits/stdc++.h>

using namespace std;

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

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

struct Node {
  int a[5][5];
  Node() {
    for (int i = 0; i < 5; ++i) {
      for (int j = 0; j < 5; ++j) {
        a[i][j] = inf;
      }
    }
  }
  Node operator + (const Node &o) const {
    Node res;
    for (int i = 0; i < 5; ++i) {
      for (int j = 0; j < 5; ++j) {
        for (int k = 0; k < 5; ++k) {
          res.a[i][k] = min(res.a[i][k], a[i][j] + o.a[j][k]);
        }
      }
    }
    return res;
  }
};

int k, n, m, o;
int c[N][5];
Node s[4 * N];
vector<array<int, 2>> g[N];

void bld(int id = 1, int l = 0, int r = n / k - 1) {
  if (l == r) {
    for (int i = 0; i < k; ++i) {
      int ii = l * k + i;
      for (int j = 0; j < k; ++j) {
        s[id].a[i][j] = !c[ii][j] ? inf : c[ii][j];
      }
    }
    return;
  }
  int m = (l + r) / 2;
  bld(id * 2, l, m);
  bld(id * 2 + 1, m + 1, r);
  s[id] = s[id * 2] + s[id * 2 + 1];
}

Node qry(int u, int v, int id = 1, int l = 0, int r = n / k - 1) {
  if (u <= l && r <= v) {
    return s[id];
  }
  int m = (l + r) / 2;
  if (v <= m) {
    return qry(u, v, id * 2, l, m);
  }
  if (m < u) {
    return qry(u, v, id * 2 + 1, m + 1, r);
  }
  return qry(u, v, id * 2, l, m) + qry(u, v, id * 2 + 1, m + 1, r);
}

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

  cin >> k >> n >> m >> o;
  while (m--) {
    int a, b, w; cin >> a >> b >> w;
    c[a][b % k] = w;
  }
  bld();
  while (o--) {
    int a, b; cin >> a >> b;
    if (a / k == b / k) {
      cout << -1 << "\n";
    } else {
      auto d = qry(a / k, b / k - 1);
      int res = d.a[a % k][b % k];
      cout << (res == inf ? -1 : res) << "\n";
    }
  }
  return 0;
}

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