Submission #1334290
Source Code Expand
fn getline() -> String{ let mut __ret = String::new(); std::io::stdin().read_line(&mut __ret).ok(); return __ret; } struct UnionFind { par: Vec<usize>, rank: Vec<usize>, } impl UnionFind { fn new(n: usize) -> UnionFind { let mut vec = vec![0;n]; for i in 0..n { vec[i] = i; } UnionFind { par : vec, rank : vec![0;n], } } fn find(&mut self, x: usize) -> usize { if x == self.par[x] { x }else{ let par = self.par[x]; let res = self.find(par); self.par[x] = res; res } } fn same(&mut self, a: usize, b: usize) -> bool { self.find(a) == self.find(b) } fn unite(&mut self, a: usize, b: usize){ let apar = self.find(a); let bpar = self.find(b); if self.rank[apar] > self.rank[bpar] { self.par[bpar] = apar; }else{ self.par[apar] = bpar; if self.rank[apar] == self.rank[bpar] { self.rank[bpar] += 1; } } } } fn printvec<T: std::fmt::Display>(x: &Vec<T>){ for v in x { print!("{} ",v); } println!(""); } fn main() { let s = getline(); let inp:Vec<_> = s.trim().split(' ').collect(); let n: usize = inp[0].parse().unwrap(); let q: usize = inp[1].parse().unwrap(); let mut uf = UnionFind::new(n); // printvec(&uf.par); for _ in 0..q { let s = getline(); let inp:Vec<_> = s.trim().split(' ').collect(); let p: i32 = inp[0].parse().unwrap(); let a: usize = inp[1].parse().unwrap(); let b: usize = inp[2].parse().unwrap(); if p == 0 { uf.unite(a,b); // printvec(&(uf.par)); }else{ if uf.same(a,b) { println!("Yes"); }else{ println!("No"); } } } }
Submission Info
Submission Time | |
---|---|
Task | B - Union Find |
User | sntea |
Language | Rust (1.15.1) |
Score | 100 |
Code Size | 2059 Byte |
Status | AC |
Exec Time | 441 ms |
Memory | 6908 KB |
Compile Error
warning: function is never used: `printvec`, #[warn(dead_code)] on by default --> ./Main.rs:54:1 | 54 | fn printvec<T: std::fmt::Display>(x: &Vec<T>){ | _^ starting here... 55 | | for v in x { 56 | | print!("{} ",v); 57 | | } 58 | | println!(""); 59 | | } | |_^ ...ending here
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
All | 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 2 ms | 4352 KB |
subtask_01_01.txt | AC | 265 ms | 4604 KB |
subtask_01_02.txt | AC | 2 ms | 6396 KB |
subtask_01_03.txt | AC | 427 ms | 5116 KB |
subtask_01_04.txt | AC | 432 ms | 6908 KB |
subtask_01_05.txt | AC | 26 ms | 4352 KB |
subtask_01_06.txt | AC | 23 ms | 6396 KB |
subtask_01_07.txt | AC | 434 ms | 4860 KB |
subtask_01_08.txt | AC | 426 ms | 6908 KB |
subtask_01_09.txt | AC | 2 ms | 4352 KB |
subtask_01_10.txt | AC | 2 ms | 6396 KB |
subtask_01_11.txt | AC | 424 ms | 4988 KB |
subtask_01_12.txt | AC | 432 ms | 6908 KB |
subtask_01_13.txt | AC | 356 ms | 4732 KB |
subtask_01_14.txt | AC | 3 ms | 6396 KB |
subtask_01_15.txt | AC | 427 ms | 4860 KB |
subtask_01_16.txt | AC | 441 ms | 6908 KB |
subtask_01_17.txt | AC | 258 ms | 6652 KB |
subtask_01_18.txt | AC | 252 ms | 6652 KB |