結果
問題 | No.3072 Speedrun Query |
ユーザー |
|
提出日時 | 2025-03-21 22:23:06 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 137 ms / 2,500 ms |
コード長 | 2,843 bytes |
コンパイル時間 | 13,139 ms |
コンパイル使用メモリ | 379,356 KB |
実行使用メモリ | 66,432 KB |
最終ジャッジ日時 | 2025-03-21 22:23:24 |
合計ジャッジ時間 | 17,542 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#[allow(unused_imports)] use std::{ cell::RefCell, convert::{Infallible, TryFrom, TryInto as _}, fmt::{self, Debug, Display, Formatter,}, fs::{File}, hash::{Hash, Hasher}, iter::{Product, Sum}, marker::PhantomData, ops::{Add, AddAssign, Sub, SubAssign, Div, DivAssign, Mul, MulAssign, Neg, RangeBounds}, str::{FromStr, SplitWhitespace}, sync::{atomic::{self, AtomicU32, AtomicU64}, Once}, collections::{*, btree_map::Range}, mem::{swap}, cmp::{self, Reverse, Ordering, Eq, PartialEq, PartialOrd}, thread::LocalKey, f64::consts::PI, time::Instant, rc::Rc, ptr::null_mut, io::{self, stdin, Read, read_to_string, BufWriter, BufReader, stdout, Write}, }; #[allow(unused_imports)] use proconio::{input, input_interactive, marker::{*}}; #[allow(unused_imports)] //use rand::{thread_rng, Rng, seq::SliceRandom}; #[allow(unused_imports)] //use ac_library::{*}; #[allow(dead_code)] const INF: i64 = 1<<61; #[allow(dead_code)] const MOD: i64 = 998244353; #[allow(dead_code)] const D: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)]; use proconio::fastout; #[fastout] fn main() { input!{ n: usize, ka: usize, kb: usize, a: [Usize1; ka], b: [Usize1; kb], q: usize, query: [(Usize1, Usize1); q], } let mut edge = vec![Vec::new(); n+2]; for i in 0..n-1{ edge[i].push((i+1, 1)); edge[i+1].push((i, 1)); } for &v in &a{ edge[n].push((v, 0)); edge[v].push((n, 0)); } for &v in &b{ edge[v].push((n+1, 0)); edge[n+1].push((v, 0)); } let mut dist1 = vec![1<<30; n+2]; let mut dist2 = vec![1<<30; n+2]; dist1[n] = 0; dist2[n+1] = 0; let mut stack = VecDeque::from([n]); while let Some(p) = stack.pop_front(){ for &(nex, d) in &edge[p]{ if dist1[nex] <= n+2{continue} if dist1[nex] > dist1[p]+d{ if d==0{ stack.push_front(nex); dist1[nex] = dist1[p]; } else { stack.push_back(nex); dist1[nex] = dist1[p]+d; } } } } stack.push_back(n+1); while let Some(p) = stack.pop_front(){ for &(nex, d) in &edge[p]{ if dist2[nex] <= n+2{continue} if dist2[nex] > dist2[p]+d{ if d==0{ stack.push_front(nex); dist2[nex] = dist2[p]; } else { stack.push_back(nex); dist2[nex] = dist2[p]+d; } } } } let r = dist1[n+1]; for &(u, v) in &query{ let ans = (v-u).min(dist1[u]+dist1[v]).min(dist2[u]+dist2[v]).min(dist1[u]+dist2[v]+r).min(dist2[u]+dist1[v]+r); println!("{}", ans); } }