結果
問題 | No.3072 Speedrun Query |
ユーザー |
![]() |
提出日時 | 2025-03-21 21:52:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 871 ms / 2,500 ms |
コード長 | 1,853 bytes |
コンパイル時間 | 3,818 ms |
コンパイル使用メモリ | 280,428 KB |
実行使用メモリ | 17,408 KB |
最終ジャッジ日時 | 2025-03-21 21:52:32 |
合計ジャッジ時間 | 17,709 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,N) for(i=0;i<N;i++) #define ll long long int main(void){ ll N,KA,KB; ll da[300009]; ll db[300009]; ll dab=INT64_MAX; ll Q; ll S[300009]; ll T[300009]; ll i,j,k; rep(i,300009){ da[i]=INT64_MAX; db[i]=INT64_MAX; } queue<ll>qa,qb; cin>>N>>KA>>KB; rep(i,KA){ cin>>j; da[j]=0; qa.push(j); } rep(i,KB){ cin>>j; db[j]=0; qb.push(j); } cin>>Q; rep(i,Q)cin>>S[i]>>T[i]; while(!qa.empty()){ ll now=qa.front();qa.pop(); ll next; next=now-1; if(next!=0){ if(da[next]==INT64_MAX){ da[next]=da[now]+1; qa.push(next); } } next=now+1; if(next!=N+1){ if(da[next]==INT64_MAX){ da[next]=da[now]+1; qa.push(next); } } } while(!qb.empty()){ ll now=qb.front();qb.pop(); ll next; next=now-1; if(next!=0){ if(db[next]==INT64_MAX){ db[next]=db[now]+1; qb.push(next); } } next=now+1; if(next!=N+1){ if(db[next]==INT64_MAX){ db[next]=db[now]+1; qb.push(next); } } } for(i=1;i<=N;i++){ if(da[i]==0){ dab=min(dab,db[i]); } } rep(i,Q){ ll ans=abs(S[i]-T[i]); ll sum; sum=db[S[i]]+dab+da[T[i]]; ans=min(ans,sum); sum=da[S[i]]+dab+db[T[i]]; ans=min(ans,sum); sum=da[S[i]]+da[T[i]]; ans=min(ans,sum); sum=db[S[i]]+db[T[i]]; ans=min(ans,sum); cout<<ans<<endl; } return 0; }