結果
問題 | No.1170 Never Want to Walk |
ユーザー |
![]() |
提出日時 | 2020-08-14 23:00:30 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 1,956 bytes |
コンパイル時間 | 13,239 ms |
コンパイル使用メモリ | 404,172 KB |
実行使用メモリ | 5,912 KB |
最終ジャッジ日時 | 2024-10-10 16:21:25 |
合計ジャッジ時間 | 16,149 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
struct UnionFind { par: Vec<usize>, sizes: Vec<usize>, } impl UnionFind { fn new(n: usize) -> UnionFind { UnionFind { par: (0..n).collect(), sizes: vec![1; n], } } fn find(&mut self, x: usize) -> usize { if x == self.par[x] { x } else { self.par[x] = self.find(self.par[x]); self.par[x] } } fn unite(&mut self, mut x: usize, mut y: usize) { x = self.find(x); y = self.find(y); if x == y { return; } if self.sizes[x] > self.sizes[y] { std::mem::swap(&mut x, &mut y); } self.par[x] = y; self.sizes[y] += self.sizes[x]; } fn size(&mut self, mut x: usize) -> usize { x = self.find(x); self.sizes[x] } } use std::io::{BufRead, Write}; fn main() { let stdin = std::io::stdin(); let stdout = std::io::stdout(); let mut reader = std::io::BufReader::new(stdin.lock()); let mut writer = std::io::BufWriter::new(stdout.lock()); let (n, a, b): (usize, i32, i32) = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), ) }; let x: Vec<i32> = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let iter = buf.split_whitespace(); iter.map(|x| x.parse().unwrap()).collect() }; let mut uf = UnionFind::new(n); let mut p = 0; for i in 0..n { while p < n && x[p] <= x[i] + b { if x[i] + a <= x[p] { uf.unite(i, p); } p += 1; } p -= 1; } for i in 0..n { writeln!(writer, "{}", uf.size(i)).unwrap(); } }