結果
| 問題 | No.2296 Union Path Query (Hard) |
| ユーザー |
 akakimidori
|
| 提出日時 | 2023-03-15 02:24:36 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 998 ms / 7,000 ms |
| コード長 | 6,151 bytes |
| コンパイル時間 | 14,395 ms |
| コンパイル使用メモリ | 378,492 KB |
| 実行使用メモリ | 69,248 KB |
| 最終ジャッジ日時 | 2024-11-23 04:37:19 |
| 合計ジャッジ時間 | 46,435 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 45 |
ソースコード
//---------- begin union_find ----------pub struct DSU {p: Vec<i32>,}impl DSU {pub fn new(n: usize) -> DSU {assert!(n < std::i32::MAX as usize);DSU { p: vec![-1; n] }}pub fn init(&mut self) {self.p.iter_mut().for_each(|p| *p = -1);}pub fn root(&self, mut x: usize) -> usize {assert!(x < self.p.len());while self.p[x] >= 0 {x = self.p[x] as usize;}x}pub fn same(&self, x: usize, y: usize) -> bool {assert!(x < self.p.len() && y < self.p.len());self.root(x) == self.root(y)}pub fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {assert!(x < self.p.len() && y < self.p.len());let mut x = self.root(x);let mut y = self.root(y);if x == y {return None;}if self.p[x] > self.p[y] {std::mem::swap(&mut x, &mut y);}self.p[x] += self.p[y];self.p[y] = x as i32;Some((x, y))}pub fn parent(&self, x: usize) -> Option<usize> {assert!(x < self.p.len());let p = self.p[x];if p >= 0 {Some(p as usize)} else {None}}pub fn sum<F>(&self, mut x: usize, mut f: F) -> usizewhereF: FnMut(usize),{while let Some(p) = self.parent(x) {f(x);x = p;}x}pub fn size(&self, x: usize) -> usize {assert!(x < self.p.len());let r = self.root(x);(-self.p[r]) as usize}}//---------- end union_find ----------// ---------- begin scannner ----------#[allow(dead_code)]mod scanner {use std::str::FromStr;pub struct Scanner<'a> {it: std::str::SplitWhitespace<'a>,}impl<'a> Scanner<'a> {pub fn new(s: &'a String) -> Scanner<'a> {Scanner {it: s.split_whitespace(),}}pub fn next<T: FromStr>(&mut self) -> T {self.it.next().unwrap().parse::<T>().ok().unwrap()}pub fn next_bytes(&mut self) -> Vec<u8> {self.it.next().unwrap().bytes().collect()}pub fn next_chars(&mut self) -> Vec<char> {self.it.next().unwrap().chars().collect()}pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {(0..len).map(|_| self.next()).collect()}}}// ---------- end scannner ----------use std::io::Write;fn main() {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();let mut sc = scanner::Scanner::new(&s);let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());run(&mut sc, &mut out);}fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {let n: usize = sc.next();let mut x: usize = sc.next();let q: usize = sc.next();let mut dsu = DSU::new(n);let mut g = vec![vec![]; n];let mut depth = vec![(0, 0); n]; // 根からの辺の個数、重みの和let mut table = vec![vec![0; n]; 18];let mut diameter = (0..n).map(|v| (0, v, v)).collect::<Vec<_>>(); // 直径, 端点for table in table.iter_mut() {for (j, t) in table.iter_mut().enumerate() {*t = j;}}for _ in 0..q {let op: u8 = sc.next();if op == 1 {let v: usize = sc.next();let w: i64 = sc.next();let u = dsu.root(v);g[v].push((x, w));g[x].push((v, w));let (p, c) = dsu.unite(x, v).unwrap();let (a, b) = if u == c { (x, v) } else { (v, x) };let topo = bfs(b, a, &g);for &(v, p, c, d) in topo.iter() {table[0][v] = p;let p = depth[a];depth[v] = (p.0 + 1 + c, p.1 + w + d);}for i in 1..table.len() {for &(v, _, _, _) in topo.iter() {table[i][v] = table[i - 1][table[i - 1][v]];}}let a = diameter[p];let b = diameter[c];let mut next = a.max(b);for a in [a.1, a.2].iter() {for b in [b.1, b.2].iter() {let d = dist(*a, *b, &depth, &table);next = (d, *a, *b).max(next);}}diameter[p] = next;} else if op == 2 {let u: usize = sc.next();let v: usize = sc.next();if dsu.same(u, v) {let d = dist(u, v, &depth, &table);writeln!(out, "{}", d).ok();x += d as usize;} else {writeln!(out, "-1").ok();}} else if op == 3 {let v: usize = sc.next();writeln!(out, "{}", diameter[dsu.root(v)].0).ok();} else {let value: usize = sc.next();x += value;}x %= n;}}pub fn bfs(src: usize, p: usize, g: &[Vec<(usize, i64)>]) -> Vec<(usize, usize, usize, i64)> {let mut topo = vec![(src, p, 0, 0)];for i in 0.. {if i >= topo.len() {break;}let (v, p, c, d) = topo[i];for &(u, w) in g[v].iter().filter(|e| e.0 != p) {topo.push((u, v, c + 1, d + w));}}topo}pub fn dist(x: usize, y: usize, depth: &[(usize, i64)], table: &[Vec<usize>]) -> i64 {let mut a = x;let mut b = y;if depth[a].0 < depth[b].0 {std::mem::swap(&mut a, &mut b);}for (i, table) in table.iter().enumerate().rev() {if (depth[a].0 - depth[b].0) >> i & 1 == 1 {a = table[a];}}if a == b {return depth[x].1.max(depth[y].1) - depth[a].1;}for table in table.iter().rev() {if table[a] != table[b] {a = table[a];b = table[b];}}let lca = table[0][a];depth[x].1 + depth[y].1 - 2 * depth[lca].1}