This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;
const int INF = 1e9;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k, n, m, o, a, b, t, rows, compRows, index;
ve<ve<pair<int, int>>> Graph;
ve<tuple<int, int, int, int>> DiffComp;
ve<tuple<int, int, int>> SameComp;
ve<int> Ans, T, TNew;
ve<ve<int>> TF, TFNew, TB, TBNew;
cin >> k >> n >> m >> o;
Graph = ve<ve<pair<int, int>>>(n);
Ans = ve<int>(o);
if (n % k == 0) rows = n / k;
else rows = n / k + 1;
compRows = sqrt(rows);
for (int i = 0; i < m; i++) {
cin >> a >> b >> t;
Graph[a].push_back({b, t});
}
for (int i = 0; i < o; i++) {
cin >> a >> b;
if (b >= a) {
int ca = a / k / compRows;
int cb = b / k / compRows;
if (ca == cb) SameComp.push_back({a, b, i});
else DiffComp.push_back({ca, b, a, i});
}
}
for (tuple<int, int, int> p : SameComp) {
tie(a, b, index) = p;
int r = a / k;
T = ve<int>(k, INF);
T[a % k] = 0;
while (r != b / k) {
TNew = ve<int>(k, INF);
for (int i = 0; i < k; i++) {
if (T[i] != INF) {
for (pair<int, int> e : Graph[r * k + i]) {
int tNew = T[i] + e.second;
TNew[e.first % k] = min(TNew[e.first % k], tNew);
}
}
}
T = TNew;
r++;
}
if (T[b % k] == INF) Ans[index] = -1;
else Ans[index] = T[b % k];
}
sort(DiffComp.begin(), DiffComp.end());
auto it = DiffComp.begin();
while (it != DiffComp.end()) {
int c = get<0>(*it);
int rf = (c + 1) * compRows - 1;
TF = ve<ve<int>>(k, ve<int>(k, INF));
for (int i = 0; i < k; i++) TF[i][i] = 0;
while (it != DiffComp.end() && get<0>(*it) == c) {
b = get<1>(*it);
a = get<2>(*it);
index = get<3>(*it);
while (rf != b / k) {
TFNew = ve<ve<int>>(k, ve<int>(k, INF));
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (TF[i][j] != INF) {
for (pair<int, int> e : Graph[rf * k + j]) {
int tNew = TF[i][j] + e.second;
TFNew[i][e.first % k] = min(TFNew[i][e.first % k], tNew);
}
}
}
}
TF = TFNew;
rf++;
}
int rb = (c + 1) * compRows - 1;
TB = TF;
while (rb != a / k) {
rb--;
TBNew = ve<ve<int>>(k, ve<int>(k, INF));
for (int i = 0; i < k; i++) {
for (pair<int, int> e : Graph[rb * k + i]) {
for (int j = 0; j < k; j++) {
int tNew = TF[e.first % k][j] + e.second;
TBNew[i][j] = min(TBNew[i][j], tNew);
}
}
}
TB = TBNew;
}
if (TB[a % k][b % k] == INF) Ans[index] = -1;
else Ans[index] = TB[a % k][b % k];
it++;
}
}
for (int i = 0; i < o; i++) {
cout << Ans[i] << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |