Submission #1261991

#TimeUsernameProblemLanguageResultExecution timeMemory
1261991dangheoToll (BOI17_toll)C++20
49 / 100
52 ms29800 KiB
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <iomanip> #include <numeric> #include <vector> #include <queue> #include <stack> #include <string> #define hyathu main #define popcorn __builtin_popcount using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; constexpr int mmb = 5e4 + 69; const ld pi = atan(1) * 4; int n, q, m, k, a, b; ll d[mmb][15][5]; void readData(){ cin >> k >> n >> m >> q; fill(d[0][0], d[n + 1][0], 4e18); int x, y; ll w; for(int i = 1; i <= m; ++i){ cin >> x >> y >> w;; y %= k; d[x][0][y] = min(d[x][0][y], w); } } void solve(){ for(int j = 1; j <= 14; ++j){ for(int i = 0; i < n; ++i){ if(i / k + (1 << j) > n / k) break; int ly = i / k + (1 << (j - 1)); for(int nx = 0; nx < k; ++nx){ for(int bt = 0; bt < k; ++bt) d[i][j][nx] = min(d[i][j][nx], d[i][j - 1][bt] + d[ly * k + bt][j - 1][nx]); } } } while(q--){ cin >> a >> b; int la = a / k; int lb = b / k; int step = 14; ll mn[5], nx[5]; fill(mn, mn + k, 4e18); fill(nx, nx + k, 4e18); mn[a % k] = 0; while(step >= 0){ if(la + (1 << step) <= lb){ int nl = la + (1 << step); for(int i = 0; i < k; ++i){ for(int j = 0; j < k; ++j) nx[j] = min(nx[j], mn[i] + d[la * k + i][step][j]); } copy(nx, nx + k, mn); la = nl; fill(nx, nx + k, 4e18); } --step; } cout << (mn[b % k] == 4e18 ? -1 : mn[b % k]) << "\n"; } } #define filename "test" int hyathu(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #ifdef dangheo freopen("test.inp", "r", stdin); //freopen("test.out", "w", stdout); #else //freopen(filename".INP", "r", stdin); //freopen(filename".OUT", "w", stdout); #endif readData(); solve(); return 0; }
#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...