# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
682612 | 2023-01-16T15:19:31 Z | TS_2392 | Toll (BOI17_toll) | C++14 | 73 ms | 33724 KB |
#include <bits/stdc++.h> #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);} #define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0) #define ctz(x) __builtin_ctz(x) #define rall(x) (x).rbegin(), (x).rend() #define all(x) (x).begin(), (x).end() #define sqr(x) (x) * (x) #define eb emplace_back #define epl emplace #define lwb lower_bound #define upb upper_bound #define mp make_pair #define fi first #define se second using namespace std; typedef long long ll; typedef long double ldb; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<ll, ll> pll; typedef pair<ll, int> pli; typedef pair<int, ll> pil; typedef pair<int, int> pii; typedef pair<double, double> pdd; template<class T1, class T2> bool minimize(T1 &a, T2 b){ if(a > b){a = b; return true;} return false; } template<class T1, class T2> bool maximize(T1 &a, T2 b){ if(a < b){a = b; return true;} return false; } const int N = 5e4 + 3; const ll oo = 1e10; int k, m, n, qsn; ll d[N * 5][17][5]; int real_id(int i, int j){ return i * k + j; } int main(){ SPEED; fileIO(""); cin >> k >> n >> m >> qsn; for(int u = 0; u < n; ++u){ for(int i = 0; i < 17; ++i){ for(int j = 0; j < k; ++j) d[u][i][j] = oo; } } for(int i = 1; i <= m; ++i){ int u, v; cin >> u >> v >> d[u][0][v % k]; } for(int i = 1; i < 17; ++i) for(int u = 0; u < n; ++u){ for(int j = 0; j < k; ++j) for(int jj = 0; jj < k; ++jj){ minimize(d[u][i][j], d[u][i - 1][jj] + d[real_id(u + (1 << i - 1), jj)][i - 1][j]); } } while(qsn--){ int x, y, prefloor, lastfloor; cin >> x >> y; prefloor = x / k, lastfloor = y / k; if(prefloor < lastfloor){ int delta = lastfloor - prefloor, fstbit = ctz(delta), msk = 0; delta -= 1 << fstbit; prefloor += 1 << fstbit; ll dist[2][k]; for(int i = 0; i < k; ++i) dist[msk][i] = d[x][fstbit][i]; for(int curbit = 0; curbit < 17; ++curbit) if(delta >> curbit & 1){ msk ^= 1; for(int i = 0; i < k; ++i){ dist[msk][i] = oo; for(int ii = 0; ii < k; ++ii){ minimize(dist[msk][i], dist[msk ^ 1][ii] + d[real_id(prefloor, ii)][curbit][i]); } } prefloor += 1 << curbit; } cout << (dist[msk][y % k] < oo ? dist[msk][y % k] : -1) << '\n'; } else cout << -1 << '\n'; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 33724 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 2 ms | 980 KB | Output is correct |
6 | Correct | 2 ms | 980 KB | Output is correct |
7 | Correct | 2 ms | 980 KB | Output is correct |
8 | Correct | 44 ms | 33592 KB | Output is correct |
9 | Correct | 47 ms | 33612 KB | Output is correct |
10 | Correct | 28 ms | 33632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 73 ms | 33712 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Incorrect | 0 ms | 340 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Incorrect | 0 ms | 340 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 33724 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 2 ms | 980 KB | Output is correct |
6 | Correct | 2 ms | 980 KB | Output is correct |
7 | Correct | 2 ms | 980 KB | Output is correct |
8 | Correct | 44 ms | 33592 KB | Output is correct |
9 | Correct | 47 ms | 33612 KB | Output is correct |
10 | Correct | 28 ms | 33632 KB | Output is correct |
11 | Incorrect | 73 ms | 33712 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |