Submission #1196088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196088		aykhn	Toll (BOI17_toll)	C++20	100 / 100	71 ms	35912 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F

const int MXN = 5e4 + 5;

struct DATA
{
  int a[5][5];
};

int K;
DATA st[MXN << 2];
DATA arr[MXN];

DATA combine(DATA x, DATA y, DATA z)
{
  if (y.a[0][0] == -1) return x;
  if (x.a[0][0] == -1) return y;
  DATA res;
  for (int i = 0; i < K; i++) for (int j = 0; j < K; j++) res.a[i][j] = inf;
  for (int L = 0; L < K; L++)
  {
    for (int i = 0; i < K; i++)
    {
      for (int j = 0; j < K; j++)
      {
        for (int R = 0; R < K; R++)
        {
          res.a[L][R] = min(res.a[L][R], x.a[L][i] + z.a[i][j] + y.a[j][R]);
        }
      }
    }
  }
  return res;
}

void build(int l, int r, int x)
{
  if (l == r)
  {
    for (int i = 0; i < K; i++) for (int j = 0; j < K; j++) st[x].a[i][j] = (i == j ? 0 : inf);
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, 2*x);
  build(mid + 1, r, 2*x + 1);
  st[x] = combine(st[2*x], st[2*x + 1], arr[mid]);
}
DATA get(int l, int r, int x, int lx, int rx)
{
  if (l > rx || r < lx)
  {
    DATA x;
    x.a[0][0] = -1;
    return x;
  }
  if (l >= lx && r <= rx) return st[x];
  int mid = (l + r) >> 1;
  return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx), arr[mid]);
}

void _()
{
  int n, m, q;
  cin >> K >> n >> m >> q;
  while (n % K) n++;
  for (int i = 0; i < n / K; i++) for (int j = 0; j < K; j++) for (int k = 0; k < K; k++) arr[i].a[j][k] = inf;
  while (m--)
  {
    int a, b, t;
    cin >> a >> b >> t;
    arr[a / K].a[a % K][b % K] = min(arr[a / K].a[a % K][b % K], t);
  }
  build(0, n / K - 1, 1);
  while (q--)
  {
    int a, b;
    cin >> a >> b;
    DATA x = get(0, n / K - 1, 1, a / K, b / K);
    cout << (x.a[a % K][b % K] >= inf ? -1 : x.a[a % K][b % K]) << '\n';
  }
}

signed main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) _();
}

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