Submission #960090

#TimeUsernameProblemLanguageResultExecution timeMemory
960090sheldonToll (BOI17_toll)C++14
0 / 100
204 ms80212 KiB
#include <bits/stdc++.h> using namespace std; const int nax = 5e4 + 5; int dp[nax][16][5][5]; void combine (int first[5][5], int second[5][5], int third[5][5]) { for (int i = 0; i < 5; ++i) { for (int j = 0; j < 5; ++j) { for (int k = 0; k < 5; ++k) { third[i][k] = min (third[i][k], first[i][j] + second[j][k]); } } } } void solve() { int k, n, m, q; cin >> k >> n >> m >> q; memset (dp, 0x3f, sizeof (dp)); for (int i = 0; i < m; ++i) { int a, b, t; cin >> a >> b >> t; int loca = a / k, locb = b / k; dp[loca][0][a % k][b % k] = min (dp[loca][0][a % k][b % k], t); } for (int bit = 1; bit < 16; ++bit) { for (int i = (n - 1) / k; i >= 0; --i) { if (i + (1 << bit) > (n - 1) / k) continue; combine (dp[i][bit - 1], dp[i + (1 << bit - 1)][bit - 1], dp[i][bit]); } } while (q--) { int a, b; cin >> a >> b; int dist = b / k - a / k; int loca = a % k, locb = b % k; int at[5]; memset (at, 0x3f, sizeof (at)); bool found = 0; int node = a / k; for (int bit = 0; bit < 15; ++bit) { int new_dp[5]; memset (new_dp, 0x3f, sizeof (new_dp)); if (dist & (1 << bit)) { if (!found) { for (int i = 0; i < k; ++i) { at[i] = dp[a / k][bit][loca][i]; } found = 1; } else { for (int i = 0; i < k; ++i) { for (int j = 0; j < k; ++j) { new_dp[i] = min (new_dp[i], at[j] + dp[node][bit][j][i]); } } for (int i = 0; i < k; ++i) { at[i] = new_dp[i]; } } node += (1 << bit); } } cout << (at[locb] >= 1e9 ? -1 : at[locb]) << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); }

Compilation message (stderr)

toll.cpp: In function 'void solve()':
toll.cpp:26:27: warning: unused variable 'locb' [-Wunused-variable]
   26 |         int loca = a / k, locb =  b / k;
      |                           ^~~~
toll.cpp:33:55: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   33 |             combine (dp[i][bit - 1], dp[i + (1 << bit - 1)][bit - 1], dp[i][bit]);
      |                                                   ~~~~^~~
#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...