結果
問題 | No.3103 Butterfly Effect |
ユーザー |
![]() |
提出日時 | 2025-04-11 22:05:54 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 525 ms / 5,000 ms |
コード長 | 5,424 bytes |
コンパイル時間 | 14,651 ms |
コンパイル使用メモリ | 398,984 KB |
実行使用メモリ | 112,996 KB |
最終ジャッジ日時 | 2025-04-11 22:06:30 |
合計ジャッジ時間 | 34,124 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 50 |
コンパイルメッセージ
warning: type alias `Set` is never used --> src/main.rs:5:6 | 5 | type Set<T> = BTreeSet<T>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: type alias `Deque` is never used --> src/main.rs:6:6 | 6 | type Deque<T> = VecDeque<T>; | ^^^^^
ソースコード
use std::io::Write; use std::collections::*; type Map<K, V> = BTreeMap<K, V>; type Set<T> = BTreeSet<T>; type Deque<T> = VecDeque<T>; fn run() { input! { n: usize, q: usize, p: [(usize, usize1, usize1); q], } let ini = q + 1; let mut time = vec![q + 1; n]; time[0] = 0; let mut ans = 1; let mut unused = vec![Map::new(); n]; let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); for (q, mut x, mut y) in p { if time[x] > time[y] { std::mem::swap(&mut x, &mut y); } if q < time[x] { unused[x].insert(q, y); unused[y].insert(q, x); } else if q < time[y] { if time[y] == ini { ans += 1; } time[y] = q; let mut dfs = vec![(q, y)]; while let Some((t, v)) = dfs.pop() { while let Some((&c, &x)) = unused[v].range(t..).next() { unused[v].remove(&c); if time[x] > c { if time[x] == ini { ans += 1; } time[x] = c; dfs.push((c, x)); } } } } writeln!(out, "{}", ans).ok(); } } fn main() { run(); } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::<Vec<u8>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- // undo をuniteした情報がないときに呼ぶとREになる // snap を取るとそれまでのunite した情報が消える //---------- begin union_find ---------- pub struct DSU { parent: Vec<u32>, size: Vec<u32>, stack: Vec<Option<(u32, u32)>>, } impl DSU { pub fn new(n: usize) -> DSU { assert!(n < std::u32::MAX as usize); let mut res = DSU { parent: vec![0; n], size: vec![1; n], stack: vec![], }; res.init(); res } pub fn init(&mut self) { self.stack.clear(); for (i, (parent, size)) in self.parent.iter_mut().zip(self.size.iter_mut()).enumerate() { *parent = i as u32; *size = 1; } } pub fn root(&self, mut x: usize) -> usize { assert!(x < self.parent.len()); while self.parent[x] != x as u32 { x = self.parent[x] as usize; } x } pub fn same(&self, x: usize, y: usize) -> bool { assert!(x < self.parent.len()); assert!(y < self.parent.len()); self.root(x) == self.root(y) } pub fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> { assert!(x < self.parent.len()); assert!(y < self.parent.len()); let mut x = self.root(x); let mut y = self.root(y); if x == y { self.stack.push(None); return None; } if (self.size[x], x) < (self.size[y], y) { std::mem::swap(&mut x, &mut y); } self.size[x] += self.size[y]; self.parent[y] = x as u32; self.stack.push(Some((x as u32, y as u32))); Some((x, y)) } pub fn parent(&self, x: usize) -> Option<usize> { assert!(x < self.parent.len()); let p = self.parent[x]; if p != x as u32 { Some(p as usize) } else { None } } pub fn size(&self, x: usize) -> usize { assert!(x < self.parent.len()); let r = self.root(x); self.size[r] as usize } pub fn undo(&mut self) -> Option<(usize, usize)> { self.stack.pop().unwrap().map(|(x, y)| { let x = x as usize; let y = y as usize; self.size[x] -= self.size[y]; self.parent[y] = y as u32; (x, y) }) } pub fn snap(&mut self) { self.stack.clear(); } pub fn rollback(&mut self) { while !self.stack.is_empty() { self.undo(); } } } //---------- end union_find ----------