Submission #654685

#TimeUsernameProblemLanguageResultExecution timeMemory
654685HaYoungJoonToll (BOI17_toll)C++14
100 / 100
124 ms167560 KiB
#include <bits/stdc++.h> #define ll long long #define INF 1e18 using namespace std; ll dp[50001][17][5][5],K,n,m,Q, ans[5][5], tmp[5][5]; void combine(ll target[5][5], ll a[5][5], ll b[5][5]) { for (int i = 0; i < K; i++) for (int j = 0; j < K; j++) { target[i][j] = INF; for (int mid = 0; mid < K; mid++) target[i][j] = min(target[i][j],a[i][mid] + b[mid][j]); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> K >> n >> m >> Q; int maxU = n/K + (n % K != 0); for (int i = 0; i <= maxU; i++) for (int j = 0; j <= 16; j++) for (int k = 0; k < K; k++) for (int l = 0; l < K; l++) dp[i][j][k][l] = INF; for (int i = 1; i <= m; i++) { int u,v,w; cin >> u >> v >> w; dp[u/K][0][u%K][v%K] = w; } for (int i = maxU; i >= 0; i--) { for (int j = 1; i + (1 << j) - 1 <= maxU; j++) { combine(dp[i][j],dp[i][j-1],dp[i + (1 << (j-1))][j-1]); } } while (Q--) { int u,v; cin >> u >> v; int U = u/K, V = v/K; for (int i = 0; i < K; i++) for (int j = 0; j < K; j++) if (i != j) ans[i][j] = INF; else ans[i][j] = 0; for (int i = 16; i >= 0; i--) { if (U + (1 << i) <= V) { for (int i = 0; i < K; i++) for (int j = 0; j < K; j++) tmp[i][j] = ans[i][j]; combine(ans,tmp,dp[U][i]); U += (1 << i); } } if (ans[u % K][v % K] == INF) cout << "-1\n"; else cout << ans[u % K][v % K] << '\n'; } return 0; } /* 5 14 5 5 0 5 9 5 12 10 0 7 7 7 12 8 4 7 10 0 12 0 5 0 7 7 12 0 13 */
#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...