結果
問題 | No.2294 Union Path Query (Easy) |
ユーザー | akakimidori |
提出日時 | 2023-03-14 23:27:14 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 221 ms / 4,000 ms |
コード長 | 5,067 bytes |
コンパイル時間 | 14,952 ms |
コンパイル使用メモリ | 377,308 KB |
実行使用メモリ | 57,856 KB |
最終ジャッジ日時 | 2024-05-02 03:16:33 |
合計ジャッジ時間 | 27,043 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 221 ms
57,344 KB |
testcase_04 | AC | 119 ms
35,072 KB |
testcase_05 | AC | 99 ms
31,232 KB |
testcase_06 | AC | 170 ms
57,856 KB |
testcase_07 | AC | 177 ms
57,600 KB |
testcase_08 | AC | 145 ms
55,168 KB |
testcase_09 | AC | 148 ms
55,168 KB |
testcase_10 | AC | 187 ms
57,728 KB |
testcase_11 | AC | 180 ms
57,728 KB |
testcase_12 | AC | 175 ms
57,728 KB |
testcase_13 | AC | 175 ms
56,960 KB |
testcase_14 | AC | 99 ms
54,784 KB |
testcase_15 | AC | 120 ms
56,192 KB |
testcase_16 | AC | 123 ms
56,960 KB |
testcase_17 | AC | 156 ms
56,576 KB |
testcase_18 | AC | 159 ms
56,704 KB |
testcase_19 | AC | 146 ms
56,960 KB |
testcase_20 | AC | 141 ms
56,704 KB |
testcase_21 | AC | 142 ms
56,832 KB |
testcase_22 | AC | 135 ms
56,192 KB |
testcase_23 | AC | 143 ms
56,704 KB |
testcase_24 | AC | 140 ms
56,704 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 1 ms
5,376 KB |
testcase_27 | AC | 1 ms
5,376 KB |
testcase_28 | AC | 42 ms
7,168 KB |
testcase_29 | AC | 51 ms
10,112 KB |
testcase_30 | AC | 55 ms
12,544 KB |
testcase_31 | AC | 63 ms
15,488 KB |
testcase_32 | AC | 67 ms
18,048 KB |
testcase_33 | AC | 75 ms
20,608 KB |
testcase_34 | AC | 80 ms
23,296 KB |
testcase_35 | AC | 86 ms
25,856 KB |
testcase_36 | AC | 93 ms
28,416 KB |
testcase_37 | AC | 97 ms
30,848 KB |
testcase_38 | AC | 105 ms
33,664 KB |
testcase_39 | AC | 121 ms
36,096 KB |
testcase_40 | AC | 123 ms
38,656 KB |
testcase_41 | AC | 130 ms
41,472 KB |
testcase_42 | AC | 135 ms
44,032 KB |
testcase_43 | AC | 141 ms
46,592 KB |
testcase_44 | AC | 148 ms
49,280 KB |
testcase_45 | AC | 157 ms
51,840 KB |
testcase_46 | AC | 158 ms
54,272 KB |
testcase_47 | AC | 156 ms
56,960 KB |
testcase_48 | AC | 110 ms
54,656 KB |
コンパイルメッセージ
warning: type alias `Map` is never used --> src/main.rs:96:6 | 96 | type Map<K, V> = BTreeMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: type alias `Set` is never used --> src/main.rs:97:6 | 97 | type Set<T> = BTreeSet<T>; | ^^^ warning: type alias `Deque` is never used --> src/main.rs:98:6 | 98 | type Deque<T> = VecDeque<T>; | ^^^^^
ソースコード
//---------- 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) -> usize where F: 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; use std::collections::*; type Map<K, V> = BTreeMap<K, V>; type Set<T> = BTreeSet<T>; type Deque<T> = VecDeque<T>; 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(); const MOD: usize = 998_244_353; const K: usize = 30; let mut dsu = DSU::new(n); let mut sum = vec![0; n];// 連結成分内の距離の総和 let mut cnt = vec![[0; K]; n];// 連結成分内の根からの距離のibit目が1なものの個数 let mut weight = vec![0; n];// 親への辺の重み for _ in 0..q { let op: u8 = sc.next(); if op == 1 { let v: usize = sc.next(); let mut w: usize = sc.next(); let a = dsu.sum(x, |v| w ^= weight[v]); let sa = dsu.size(a); let b = dsu.sum(v, |v| w ^= weight[v]); let sb = dsu.size(b); let (p, c) = dsu.unite(v, x).unwrap(); let (sp, sc) = if a == p {(sa, sb)} else {(sb, sa)}; sum[p] = (sum[p] + sum[c]) % MOD; weight[c] = w; let sum = &mut sum[p]; let c_cnt = std::mem::take(&mut cnt[c]); for (i, (p, c)) in cnt[p].iter_mut().zip(c_cnt.iter()).enumerate() { let a = [sp - *p, *p]; let b = [sc - *c, *c]; let w = (w >> i & 1) as usize; let cnt = (a[0] * b[w ^ 1] + a[1] * b[w]) % MOD; *sum = (*sum + cnt * (1 << i)) % MOD; *p += b[w ^ 1]; } } else if op == 2 { let u: usize = sc.next(); let v: usize = sc.next(); if dsu.same(u, v) { let mut w = 0; dsu.sum(u, |v| w ^= weight[v]); dsu.sum(v, |v| w ^= weight[v]); x += w; writeln!(out, "{}", w).ok(); } else { writeln!(out, "-1").ok(); } } else if op == 3 { let v: usize = sc.next(); writeln!(out, "{}", sum[dsu.root(v)]).ok(); } else { let value: usize = sc.next(); x += value; } x %= n; } }