# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
674676 | 2022-12-25T18:55:03 Z | AmirH | Toll (BOI17_toll) | C++14 | 85 ms | 73912 KB |
#include<iostream> #include<algorithm> #include<math.h> #include<vector> #include<bitset> #include<queue> #include<queue> #include<deque> #include<set> #include<map> #include<unordered_map> #include<list> #include<utility> #include<stack> using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll, ll> pll; typedef pair <int, int> pii; #define cl clear #define F first #define S second #define pb push_back #define Sz(x) int((x).size()) #define all(x) (x).begin(), (x).end() #define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) const int MAX_N = 5e4 + 25; const ll INF = 1e10; const int inf = 1e9; const int lgg = 17; int k, n, m, q; vector<pii> adj[MAX_N]; ll lift[MAX_N][lgg][5]; void free() { #ifndef ONLINE_JUDGE freopen("inputi.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif } void build() { for(int i = 0; i < lgg; i++) { for(int j = 0; j < n; j++) { if(i == 0) { for(auto p : adj[j]) { int x = p.first%k; lift[j][i][x] = p.second; } continue; } for(int p = 0; p < k; p++) { for(int o = 0; o < k; o++) { int x = j / k + (1 << (i - 1)); x = (x * k); x+= o; lift[j][i][p] = min(lift[j][i][p], lift[j][i-1][o] + lift[x][i - 1][p]); } } } } } void setdef() { for(int i = 0; i < MAX_N; i++) { for(int j = 0; j < lgg; j++) { for(int p = 0; p < 5; p++) lift[i][j][p] = INF; } } } ll get_min(int x, int h, int p) { if(h == 0) { if(x%k == p) return 0; else return INF; } int chap = 31 - __builtin_clz(h); ll res = INF; for(int i = 0; i < k; i++) { int y = x / k + (1 << (chap)); y = (y * k); y+= i; res = min(res, lift[x][chap][i] + get_min(y, h - (1 << chap), p)); } return res; } void solve() { build(); while(q--) { int x, y; cin >> x >> y; int hx = x / k; int hy = y / k; if(hy < hx) { cout << -1 << '\n'; } else { ll res = get_min(x, hy - hx, y%k); if(res >= INF) cout << -1 << '\n'; else cout << res << '\n'; } } } void input() { cin >> k >> n >> m >> q; for(int i = 1; i <= m; i++) { int x, y, z; cin >> x >> y >> z; adj[x].pb({y, z}); } } int main() { faster; //free(); input(); setdef(); solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 70 ms | 73912 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 85 ms | 73828 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 34644 KB | Output is correct |
2 | Runtime error | 43 ms | 70200 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 34644 KB | Output is correct |
2 | Runtime error | 43 ms | 70200 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 70 ms | 73912 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |