結果
問題 | No.3072 Speedrun Query |
ユーザー |
|
提出日時 | 2025-03-21 23:09:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 144 ms / 2,500 ms |
コード長 | 1,207 bytes |
コンパイル時間 | 2,285 ms |
コンパイル使用メモリ | 203,756 KB |
実行使用メモリ | 9,196 KB |
最終ジャッジ日時 | 2025-03-21 23:09:15 |
合計ジャッジ時間 | 6,070 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; #include<atcoder/modint> using namespace atcoder; using mint=modint998244353; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll N,KA,KB; cin>>N>>KA>>KB; vector<bool> EA(N,0),EB(N,0); for(int i=0;i<KA;i++){ int a; cin>>a; EA[a-1]=1; } for(int i=0;i<KB;i++){ int a; cin>>a; EB[a-1]=1; } queue<int> Q; vector<ll> DA(N,1e18),DB(N,1e18); for(int i=0;i<N;i++){ if(EA[i]){ Q.push(i); DA[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(DA[v]<=DA[p]+1)continue; DA[v]=DA[p]+1; Q.push(v); } } for(int i=0;i<N;i++){ if(EB[i]){ Q.push(i); DB[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(DB[v]<=DB[p]+1)continue; DB[v]=DB[p]+1; Q.push(v); } } ll M=1e9; for(int i=0;i<N;i++){ if(EB[i])M=min(M,DA[i]); } ll QQ; cin>>QQ; for(int i=0;i<QQ;i++){ ll S,T; cin>>S>>T; S--;T--; ll an=abs(S-T); an=min(an,DA[S]+DA[T]); an=min(an,DB[S]+DB[T]); an=min(an,DA[S]+DB[T]+M); an=min(an,DB[S]+DA[T]+M); cout<<an<<"\n"; } }