Submission #790331

#	Time	Username	Problem	Language	Result	Execution time	Memory
790331		tch1cherin	Toll (BOI17_toll)	C++17	100 / 100	80 ms	31824 KiB

toll

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

const int MAX_N = 50005;
int K, D[MAX_N][5][5];
const int INF = 5e8 + 5;

void chmin(int& a, int b) {
  a = a < b ? a : b;
}

struct segment_tree {
  struct node {
    int DP[5][5], nxt[5][5];
    
    node() {
      for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
          DP[i][j] = nxt[i][j] = INF;
        }
      }
    }
  };

  node merge(node& a, node& b) {
    node c;
    memcpy(c.nxt, b.nxt, sizeof b.nxt);
    for (int s1 = 0; s1 < K; s1++)
      for (int t1 = 0; t1 < K; t1++)
        for (int s2 = 0; s2 < K; s2++)
          for (int t2 = 0; t2 < K; t2++)
            chmin(c.DP[s1][t2], a.DP[s1][t1] + a.nxt[t1][s2] + b.DP[s2][t2]);

    return c;
  }
  
  int size;
  vector<node> tree;

  segment_tree(int n) : size(2 << __lg(n)), tree(4 << __lg(n)) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 5; j++) {
        tree[size + i].DP[j][j] = 0;
      }
    }
    for (int i = 0; i < n; i++) {
      memcpy(tree[size + i].nxt, D[i], sizeof D[i]);
    }
    for (int i = size - 1; i > 0; i--) {
      tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
    }
  }

  node query(int l, int r) {
    return query(l, r + 1, 1, 0, size);
  }

  node query(int l, int r, int x, int lx, int rx) {
    if (lx >= l && rx <= r) {
      return tree[x];
    } else {
      int mid = (lx + rx) / 2;
      if (mid > l && mid < r) {
        node left = query(l, r, x * 2, lx, mid);
        node right = query(l, r, x * 2 + 1, mid, rx);
        return merge(left, right); 
      } else if (mid > l) {
        return query(l, r, x * 2, lx, mid);
      } else {
        return query(l, r, x * 2 + 1, mid, rx);
      }
    }
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M, Q;
  cin >> K >> N >> M >> Q;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 5; j++) {
      for (int k = 0; k < 5; k++) {
        D[i][j][k] = INF;
      }
    }
  }
  for (int i = 0; i < M; i++) {
    int A, B, T;
    cin >> A >> B >> T;
    D[A / K][A % K][B % K] = T;
  }
  segment_tree tree((N + K - 1) / K);
  while (Q--) {
    int A, B;
    cin >> A >> B;
    if (A / K < B / K) {
      segment_tree::node value = tree.query(A / K, B / K);
      cout << (value.DP[A % K][B % K] >= INF ? -1 : value.DP[A % K][B % K]) << "\n";
    } else {
      cout << -1 << "\n";
    }
  }
}

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