Submission #1261907

#TimeUsernameProblemLanguageResultExecution timeMemory
1261907yoshi_33550336Toll (BOI17_toll)C++20
100 / 100
50 ms32808 KiB
#include <bits/stdc++.h> using namespace std; #ifndef yoshi_likes_e4 #define endl '\n' #endif #define problem "" #define multitest 0 #define debug(x) cerr << #x << " = " << x << endl; template <typename T, typename Op> struct StaticRangeProduct { static const size_t B = 8; std::vector<T> pref, suf, cur; std::vector<std::vector<T>> spt; Op op; StaticRangeProduct(std::vector<T> p, Op opr) : op(opr) { cur = p; const size_t SZ = (cur.size() + B - 1) / B * B; cur.resize(SZ); pref.resize(SZ); suf.resize(SZ); for (size_t i = 0; i < SZ; i++) { if (i % B == 0) pref[i] = cur[i]; else pref[i] = op(pref[i - 1], cur[i]); } for (size_t i = SZ - 1;; i--) { if (i % B == B - 1) suf[i] = cur[i]; else suf[i] = op(cur[i], suf[i + 1]); if (i == 0) break; } spt.assign(1, std::vector<T>(SZ / B)); for (size_t i = 0; i < SZ; i += B) spt[0][i / B] = pref[i + B - 1]; for (size_t shift = 2; shift * B < SZ; shift *= 2) { spt.push_back(std::vector<T>(SZ / B)); bool flag = 0; for (size_t k = 0; k * B < SZ; k += shift, flag ^= 1) { if (flag) { spt.back()[k] = spt[0][k]; for (size_t x = k + 1; x < std::min(SZ / B, k + shift); x++) spt.back()[x] = op(spt.back()[x - 1], spt[0][x]); } else if (k + shift <= SZ / B) { spt.back()[k + shift - 1] = spt[0][k + shift - 1]; for (size_t x = k + shift - 2;; x--) { spt.back()[x] = op(spt[0][x], spt.back()[x + 1]); if (x == k) break; } } } } } T query(size_t l, size_t r) { T res; if (l / B == r / B) { res = cur[l]; for (size_t i = l + 1; i <= r; i++) res = op(res, cur[i]); } else { res = suf[l]; if (l / B + 1 <= r / B - 1) { if (l / B + 1 == r / B - 1) res = op(res, spt[0][l / B + 1]); else { size_t lg = __lg((r / B - 1) ^ (l / B + 1)); res = op(res, spt[lg][l / B + 1]); res = op(res, spt[lg][r / B - 1]); } } res = op(res, pref[r]); } return res; } }; struct Mat { int A[5][5]; Mat() { for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) A[i][j] = 1e9; } }; auto weirdMatMul = [](Mat a, Mat b) { Mat c; for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) c.A[i][j] = 1e9; for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) for (int k = 0; k < 5; k++) c.A[i][k] = min(c.A[i][k], a.A[i][j] + b.A[j][k]); return c; }; void init() { } void Yoshi() { int K, N, M, O; cin >> K >> N >> M >> O; vector<Mat> mats(N / K + 1); while (M--) { int u, v, t; cin >> u >> v >> t; mats[u / K].A[u % K][v % K] = t; } StaticRangeProduct<Mat, decltype(weirdMatMul)> matq(mats, weirdMatMul); while (O--) { int a, b; cin >> a >> b; if (a / K >= b / K) cout << -1 << endl; else { int d = matq.query(a / K, b / K - 1).A[a % K][b % K]; if (d > 5e8) cout << -1 << endl; else cout << d << endl; } } } signed main() { #ifndef yoshi_likes_e4 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(problem ".inp", "r")) { freopen(problem ".inp", "r", stdin); freopen(problem ".out", "w", stdout); } #endif init(); int t = 1; #if multitest cin >> t; #endif while (t--) Yoshi(); }

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...