Submission #3920312
Source Code Expand
#[allow(unused_macros)] macro_rules! get { ([$t:ty] ; $n:expr) => { (0..$n) .map(|_| get!([$t])).collect::<Vec<_>>() }; ($($t:ty),+ ; $n:expr) => { (0..$n).map(|_| get!($($t),+)).collect::<Vec<_>>() }; ([$t:ty]) => { rl().split_whitespace() .map(|x| x.parse().unwrap()) .collect::<Vec<$t>>() }; ($t:ty) => { rl().parse::<$t>().unwrap() }; ($($t:ty),*) => { { let line =rl(); let mut iter = line.split_whitespace(); ($(iter.next().unwrap().parse::<$t>().unwrap()),*) } }; } fn rl() -> String { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.trim().to_string() } struct UnionFind { par: Vec<usize>, rank: Vec<usize>, } impl UnionFind { fn new(size: usize) -> UnionFind { let mut par = Vec::with_capacity(size); let mut rank = Vec::with_capacity(size); for i in 0..size { par.push(i); rank.push(0); } UnionFind { par: par, rank: rank, } } fn root(&mut self, x: usize) -> usize { if self.par[x] == x { x } else { let par = self.par[x]; let ppar = self.root(par); self.par[x] = ppar; ppar } } fn same(&mut self, x: usize, y: usize) -> bool { return self.root(x) == self.root(y); } fn unite(&mut self, x: usize, y: usize) { let px = self.root(x); let py = self.root(y); if px == py { return; } if self.rank[px] < self.rank[py] { self.par[px] = py; } else { self.par[py] = px; if self.rank[px] == self.rank[py] { self.rank[px] += 1; } } } } fn main() { let (n, m) = get!(usize, usize); let mut nv = get!([usize]); for i in nv.iter_mut() { *i -= 1; } let mut uf = UnionFind::new(n); for _ in 0..m { let (x, y) = get!(usize, usize); uf.unite(x - 1, y - 1); } let mut count = 0; for (i, x) in nv.iter().enumerate() { if uf.same(i, *x) { count += 1; } } println!("{}", count); }
Submission Info
Submission Time | |
---|---|
Task | D - Equals |
User | kuisiba |
Language | Rust (1.15.1) |
Score | 400 |
Code Size | 2419 Byte |
Status | AC |
Exec Time | 39 ms |
Memory | 6396 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 2 ms | 4352 KB |
0_001.txt | AC | 2 ms | 4352 KB |
0_002.txt | AC | 2 ms | 4352 KB |
0_003.txt | AC | 2 ms | 4352 KB |
1_004.txt | AC | 25 ms | 4352 KB |
1_005.txt | AC | 34 ms | 6396 KB |
1_006.txt | AC | 39 ms | 6396 KB |
1_007.txt | AC | 2 ms | 4352 KB |
1_008.txt | AC | 2 ms | 4352 KB |
1_009.txt | AC | 2 ms | 4352 KB |
1_010.txt | AC | 2 ms | 4352 KB |
1_011.txt | AC | 2 ms | 4352 KB |
1_012.txt | AC | 2 ms | 4352 KB |
1_013.txt | AC | 2 ms | 4352 KB |
1_014.txt | AC | 3 ms | 4352 KB |
1_015.txt | AC | 2 ms | 4352 KB |
1_016.txt | AC | 2 ms | 4352 KB |
1_017.txt | AC | 2 ms | 4352 KB |
1_018.txt | AC | 23 ms | 4352 KB |
1_019.txt | AC | 9 ms | 6396 KB |
1_020.txt | AC | 9 ms | 6396 KB |
1_021.txt | AC | 9 ms | 6396 KB |
1_022.txt | AC | 39 ms | 6396 KB |