結果
問題 | No.3072 Speedrun Query |
ユーザー |
|
提出日時 | 2025-03-21 23:53:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 172 ms / 2,500 ms |
コード長 | 874 bytes |
コンパイル時間 | 2,519 ms |
コンパイル使用メモリ | 203,360 KB |
実行使用メモリ | 10,784 KB |
最終ジャッジ日時 | 2025-03-21 23:53:51 |
合計ジャッジ時間 | 7,692 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; bool E[2][300001]; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll N,K[2],a; cin>>N>>K[0]>>K[1]; for(int t=0;t<2;t++){ for(int i=0;i<K[t];i++){ cin>>a; E[t][a-1]=1; } } queue<int> Q; vector<vector<ll>> D(2,vector<ll>(N,1e18)); for(int t=0;t<2;t++){ for(int i=0;i<N;i++)if(E[t][i]){ Q.push(i); D[t][i]=0; } while(!Q.empty()){ int p=Q.front(); Q.pop(); for(int v:{p-1,p+1}){ if(v<0||v>=N)continue; if(D[t][v]<=D[t][p]+1)continue; D[t][v]=D[t][p]+1; Q.push(v); } } } ll M=1e9; for(int i=0;i<N;i++){ if(E[1][i])M=min(M,D[0][i]); } ll QQ; cin>>QQ; for(int i=0;i<QQ;i++){ ll S,T; cin>>S>>T; S--;T--; ll an=min({abs(S-T),D[0][S]+D[0][T],D[1][S]+D[1][T],D[0][S]+D[1][T]+M,D[1][S]+D[0][T]+M}); cout<<an<<"\n"; } }