제출 #1172325

#제출 시각아이디문제언어결과실행 시간메모리
1172325crafticatToll (BOI17_toll)C++20
100 / 100
178 ms18800 KiB
#include <bits/stdc++.h> using namespace std; #define F0R(i, n) for (ll i= 0 ; i< n;i++) #define FOR(i,j,n) for (ll i = j; i< n;i++) template<typename T> using V = vector<T>; using ll = long long; using vi = V<ll>; using pi = pair<ll,ll>; ll k, n, m, o; constexpr ll INF = 1e9 + 7; V<V<vi>> base; V<vi> combine(V<vi> a, V<vi> b) { V<vi> c(k, vi(k, INF)); F0R(i, k) { F0R(j, k) { F0R(l, k) { c[i][l] = min(c[i][l], a[i][j] + b[j][l]); } } } return c; } struct Seg { Seg *left = nullptr, *right = nullptr; ll l, r, mid; V<vi> to; Seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) { if (r -l > 1) { left = new Seg(l, mid); right = new Seg(mid, r); to = combine(left->to, right->to); } else { to = base[l]; } } V<vi> q(ll a, ll b) { if (b <= l or a >= r) return {}; if (a<=l and b>= r) { return to; } auto r1 = left->q(a,b); auto r2 = right->q(a,b); if (r1.empty()) return r2; if (r2.empty()) return r1; return combine(r1, r2); } }; int main() { cin >> k >> n >> m >> o; base.resize((n + 1) / k, V<vi>(k, vi(k, INF))); F0R(i, m) { ll a, b, c; cin >> a >> b >> c; base[a / k][a % k][b % k] = c; } Seg* seg = new Seg(0, (n +1) / k); F0R(i, o) { ll a, b; cin >> a >> b; auto r = seg->q(a / k, b / k); if (r.empty() or r[a % k][b % k] >= INF) cout << "-1" << "\n"; else { cout << r[a % k][b % k] << "\n"; } } }
#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...