Submission #1222265

#TimeUsernameProblemLanguageResultExecution timeMemory
1222265j_vdd16Toll (BOI17_toll)C++20
7 / 100
139 ms71252 KiB
#include <algorithm> #include <bitset> #include <cstdint> #include <cstring> #include <iostream> #include <limits.h> #include <math.h> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #include <chrono> #include <bit> #include <climits> #define loop(X, N) for(int X = 0; X < (N); X++) #define all(V) V.begin(), V.end() #define rall(V) V.rbegin(), V.rend() using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vector<ii>> vvii; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; int main() { int k, n, m, o; cin >> k >> n >> m >> o; int l = n / k; const int P = 16; vector<vector<vvi>> dp(l + 1, vector<vvi>(P, vvi(k, vi(k, INT_MAX / 2)))); dp[l] = vector<vvi>(P, vvi(k, vi(k, 0))); loop(i, m) { int a, b, t; cin >> a >> b >> t; dp[a / k][0][a % k][b % k] = t; } for (int p = 1; p < P; p++) { for (int layer = 0; layer < l; layer++) { const vvi& connector1 = dp[layer][p - 1]; const vvi& connector2 = dp[min(l, layer + (1 << (p - 1)))][p - 1]; vvi& connector = dp[layer][p]; for (int i1 = 0; i1 < k; i1++) { for (int i2 = 0; i2 < k; i2++) { for (int i3 = 0; i3 < k; i3++) { connector[i1][i3] = min(connector[i1][i3], connector1[i1][i2] + connector2[i2][i3]); } } } } } loop(order, o) { int a, b; cin >> a >> b; int l1 = a / k; int l2 = b / k; if (l1 == l2) { cout << -1 << endl; } vi cost(k, INT_MAX / 2); cost[a % k] = 0; for (int p = P - 1; p >= 0; p--) { int diff = l2 - l1; if ((diff & (1 << p)) == 0) continue; const vvi& connector = dp[l1][p]; vi newCost(k, INT_MAX / 2); for (int i = 0; i < k; i++) { for (int j = 0; j < k; j++) { newCost[j] = min(newCost[j], cost[i] + connector[i][j]); } } swap(cost, newCost); l1 += (1 << p); } int ans = cost[b % k]; if (ans == INT_MAX / 2) cout << -1 << endl; else cout << ans << endl; } }
#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...