結果
問題 | No.826 連絡網 |
ユーザー |
|
提出日時 | 2023-11-18 18:35:07 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 255 ms / 2,000 ms |
コード長 | 3,618 bytes |
コンパイル時間 | 11,023 ms |
コンパイル使用メモリ | 401,764 KB |
実行使用メモリ | 17,484 KB |
最終ジャッジ日時 | 2024-09-26 05:53:27 |
合計ジャッジ時間 | 14,353 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#![allow(unused_imports)]// use itertools::Itertools;// use proconio::input;// use proconio::marker::*;use std::cmp::Reverse;use std::collections::*;fn main() {input! {n:usize,p:usize,}let mut uf = UnionFindTree::new(n + 1);for i in 2..=n {for j in (i..=n).step_by(i) {uf.unite(i, j);}}let ans = uf.size(p);println!("{}", ans);}use unionfindtree::*;mod unionfindtree{pub struct UnionFindTree {par: Vec<usize>,rank: Vec<usize>,size: Vec<usize>,}impl UnionFindTree {pub fn new(n: usize) -> Self {Self {par: (0..n).collect::<Vec<_>>(),rank: vec![0; n],size: vec![1; n],}}#[allow(dead_code)]pub fn same(&mut self, v1: usize, v2: usize) -> bool {self.root(v1) == self.root(v2)}#[allow(dead_code)]pub fn size(&mut self, v: usize) -> usize {let v_root = self.root(v);self.size[v_root]}#[allow(dead_code)]pub fn root(&mut self, v: usize) -> usize {if self.par[v]!=v{self.par[v]=self.root(self.par[v]);}self.par[v]}pub fn unite(&mut self, v1: usize, v2: usize) {let mut v1_root = self.root(v1);let mut v2_root = self.root(v2);if v1_root == v2_root {return;}if self.rank[v1_root] < self.rank[v2_root] {std::mem::swap(&mut v1_root,&mut v2_root);}self.par[v2_root] = v1_root;self.size[v1_root] += self.size[v2_root];if self.rank[v1_root] == self.rank[v2_root] {self.rank[v1_root] += 1;}}#[allow(dead_code)]pub fn nofcc(&mut self) -> usize {let n = self.par.len();(0..n).map(|v| self.root(v)).collect::<std::collections::HashSet<usize>>().len()}}}mod input {#[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, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}}