結果
問題 |
No.3072 Speedrun Query
|
ユーザー |
![]() |
提出日時 | 2025-03-21 23:28:52 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 744 ms / 2,500 ms |
コード長 | 1,681 bytes |
コンパイル時間 | 5,959 ms |
コンパイル使用メモリ | 333,168 KB |
実行使用メモリ | 74,848 KB |
最終ジャッジ日時 | 2025-03-21 23:29:15 |
合計ジャッジ時間 | 20,122 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define FAST_IO \ ios::sync_with_stdio(false); \ cin.tie(0); const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; vector<i64> dijkstra(int s, vector<vector<pair<int, int>>> G) { vector<i64> dist(G.size(), INF); dist[s] = 0; priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq; pq.push({0, s}); while (pq.size() > 0) { auto [d, u] = pq.top(); pq.pop(); if (dist[u] < d) continue; for (auto [v, c] : G[u]) { if (dist[v] > dist[u] + c) { dist[v] = dist[u] + c; pq.push({dist[v], v}); } } } return dist; } int main() { FAST_IO auto ans = 0LL; int N, KA, KB; cin >> N >> KA >> KB; vector<int> a(KA), b(KB); for (auto& x : a) cin >> x; for (auto& x : b) cin >> x; vector<vector<pair<int, int>>> G(N + 2); for (int i = 0; i < N - 1; i ++) { G[i].push_back({i + 1, 1}); G[i + 1].push_back({i, 1}); } for (auto x : a) { x --; G[N].push_back({x, 0}); G[x].push_back({N, 0}); } for (auto x : b) { x --; G[N + 1].push_back({x, 0}); G[x].push_back({N + 1, 0}); } auto dist1 = dijkstra(N, G); auto dist2 = dijkstra(N + 1, G); int Q; cin >> Q; for (int i = 0; i < Q; i ++) { int s, t; cin >> s >> t; s --; t --; i64 ans = INF; ans = min(ans, dist1[s] + dist1[t]); ans = min(ans, dist2[s] + dist2[t]); ans = min(ans, (i64)abs(s - t)); cout << ans << endl; } }