結果
問題 | No.1207 グラフX |
ユーザー | o2c |
提出日時 | 2020-09-11 18:30:24 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 256 ms / 2,000 ms |
コード長 | 7,121 bytes |
コンパイル時間 | 2,534 ms |
コンパイル使用メモリ | 160,112 KB |
実行使用メモリ | 54,940 KB |
最終ジャッジ日時 | 2023-08-27 03:08:19 |
合計ジャッジ時間 | 14,148 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 212 ms
37,812 KB |
testcase_01 | AC | 216 ms
37,848 KB |
testcase_02 | AC | 209 ms
37,868 KB |
testcase_03 | AC | 212 ms
37,760 KB |
testcase_04 | AC | 210 ms
37,740 KB |
testcase_05 | AC | 247 ms
54,940 KB |
testcase_06 | AC | 249 ms
54,860 KB |
testcase_07 | AC | 256 ms
54,932 KB |
testcase_08 | AC | 153 ms
22,360 KB |
testcase_09 | AC | 170 ms
29,020 KB |
testcase_10 | AC | 244 ms
45,108 KB |
testcase_11 | AC | 253 ms
54,932 KB |
testcase_12 | AC | 154 ms
24,728 KB |
testcase_13 | AC | 60 ms
7,180 KB |
testcase_14 | AC | 202 ms
36,128 KB |
testcase_15 | AC | 171 ms
27,912 KB |
testcase_16 | AC | 65 ms
9,024 KB |
testcase_17 | AC | 128 ms
21,180 KB |
testcase_18 | AC | 107 ms
22,168 KB |
testcase_19 | AC | 103 ms
13,664 KB |
testcase_20 | AC | 210 ms
36,976 KB |
testcase_21 | AC | 8 ms
4,380 KB |
testcase_22 | AC | 125 ms
21,532 KB |
testcase_23 | AC | 138 ms
25,048 KB |
testcase_24 | AC | 96 ms
19,808 KB |
testcase_25 | AC | 205 ms
36,640 KB |
testcase_26 | AC | 156 ms
27,216 KB |
testcase_27 | AC | 191 ms
32,380 KB |
testcase_28 | AC | 178 ms
29,240 KB |
testcase_29 | AC | 185 ms
32,272 KB |
testcase_30 | AC | 84 ms
13,400 KB |
testcase_31 | AC | 49 ms
5,340 KB |
testcase_32 | AC | 72 ms
14,628 KB |
testcase_33 | AC | 74 ms
14,008 KB |
testcase_34 | AC | 162 ms
27,356 KB |
testcase_35 | AC | 9 ms
4,384 KB |
testcase_36 | AC | 163 ms
28,728 KB |
testcase_37 | AC | 134 ms
22,764 KB |
testcase_38 | AC | 31 ms
6,972 KB |
testcase_39 | AC | 78 ms
15,524 KB |
testcase_40 | AC | 31 ms
4,376 KB |
testcase_41 | AC | 103 ms
14,188 KB |
testcase_42 | AC | 1 ms
4,380 KB |
testcase_43 | AC | 1 ms
4,376 KB |
testcase_44 | AC | 1 ms
4,380 KB |
testcase_45 | AC | 194 ms
37,772 KB |
testcase_46 | AC | 187 ms
38,816 KB |
testcase_47 | AC | 188 ms
37,820 KB |
testcase_48 | AC | 186 ms
38,820 KB |
コンパイルメッセージ
warning: field `n` is never read --> Main.rs:173:5 | 172 | struct UnionFind { | --------- field in this struct 173 | n: usize, | ^ | = note: `#[warn(dead_code)]` on by default warning: associated function `size` is never used --> Main.rs:210:8 | 210 | fn size(&mut self, x: usize) -> usize { | ^^^^ warning: associated function `sizes` is never used --> Main.rs:214:8 | 214 | fn sizes(&mut self) -> Vec<usize> { | ^^^^^ warning: 3 warnings emitted
ソースコード
pub fn readln() -> String { let mut line = String::new(); ::std::io::stdin() .read_line(&mut line) .unwrap_or_else(|e| panic!("{}", e)); line } macro_rules !read {($($t :tt ) ,*;$n :expr ) =>{{let stdin =::std ::io ::stdin () ;let ret =::std ::io ::BufRead ::lines (stdin .lock () ) .take ($n ) .map (|line |{let line =line .unwrap () ;let mut it =line .split_whitespace () ;_read !(it ;$($t ) ,*) } ) .collect ::<Vec <_ >>() ;ret } } ;($($t :tt ) ,*) =>{{let line =readln () ;let mut it =line .split_whitespace () ;_read !(it ;$($t ) ,*) } } ;} macro_rules !_read {($it :ident ;[char ] ) =>{_read !($it ;String ) .chars () .collect ::<Vec <_ >>() } ;($it :ident ;[u8 ] ) =>{Vec ::from (_read !($it ;String ) .into_bytes () ) } ;($it :ident ;usize1 ) =>{$it .next () .unwrap_or_else (||panic !("input mismatch" ) ) .parse ::<usize >() .unwrap_or_else (|e |panic !("{}" ,e ) ) -1 } ;($it :ident ;[usize1 ] ) =>{$it .map (|s |s .parse ::<usize >() .unwrap_or_else (|e |panic !("{}" ,e ) ) -1 ) .collect ::<Vec <_ >>() } ;($it :ident ;[$t :ty ] ) =>{$it .map (|s |s .parse ::<$t >() .unwrap_or_else (|e |panic !("{}" ,e ) ) ) .collect ::<Vec <_ >>() } ;($it :ident ;$t :ty ) =>{$it .next () .unwrap_or_else (||panic !("input mismatch" ) ) .parse ::<$t >() .unwrap_or_else (|e |panic !("{}" ,e ) ) } ;($it :ident ;$($t :tt ) ,+) =>{($(_read !($it ;$t ) ) ,*) } ;} macro_rules! mint { ($a :expr ) => { Mint::new({ $a }) }; } const MOD: i64 = 1000000007; #[derive(Copy, Clone)] pub struct Mint(i64); impl Mint { fn new(x: i64) -> Self { Mint(x.rem_euclid(MOD)) } fn pow(self, n: usize) -> Self { match n { 0 => Mint::new(1), _ => { let mut a = self.pow(n >> 1); a *= a; if n & 1 == 1 { a *= self; } a } } } fn inv(self) -> Self { self.pow((MOD - 2) as usize) } } impl std::ops::Neg for Mint { type Output = Mint; fn neg(self) -> Self::Output { Self::new(-self.0) } } impl std::ops::AddAssign<Mint> for Mint { fn add_assign(&mut self, rhs: Self) { self.0 += rhs.0; self.0 %= MOD; } } impl std::ops::AddAssign<i64> for Mint { fn add_assign(&mut self, rhs: i64) { *self += Mint::new(rhs); } } impl std::ops::AddAssign<usize> for Mint { fn add_assign(&mut self, rhs: usize) { *self += Mint::new(rhs as i64); } } impl<T> std::ops::Add<T> for Mint where Mint: std::ops::AddAssign<T>, { type Output = Self; fn add(self, other: T) -> Self { let mut res = self; res += other; res } } impl std::ops::SubAssign<Mint> for Mint { fn sub_assign(&mut self, rhs: Self) { self.0 -= rhs.0; if self.0 < 0 { self.0 += MOD; } } } impl std::ops::SubAssign<i64> for Mint { fn sub_assign(&mut self, rhs: i64) { *self -= Mint::new(rhs); } } impl std::ops::SubAssign<usize> for Mint { fn sub_assign(&mut self, rhs: usize) { *self -= Mint::new(rhs as i64); } } impl<T> std::ops::Sub<T> for Mint where Mint: std::ops::SubAssign<T>, { type Output = Self; fn sub(self, other: T) -> Self { let mut res = self; res -= other; res } } impl std::ops::MulAssign<Mint> for Mint { fn mul_assign(&mut self, rhs: Self) { self.0 *= rhs.0; self.0 %= MOD; } } impl std::ops::MulAssign<i64> for Mint { fn mul_assign(&mut self, rhs: i64) { *self *= Mint::new(rhs); } } impl std::ops::MulAssign<usize> for Mint { fn mul_assign(&mut self, rhs: usize) { *self *= Mint::new(rhs as i64); } } impl<T> std::ops::Mul<T> for Mint where Mint: std::ops::MulAssign<T>, { type Output = Self; fn mul(self, other: T) -> Self { let mut res = self; res *= other; res } } impl std::ops::DivAssign<Mint> for Mint { fn div_assign(&mut self, rhs: Self) { *self *= rhs.inv(); } } impl std::ops::DivAssign<i64> for Mint { fn div_assign(&mut self, rhs: i64) { *self /= Mint::new(rhs); } } impl std::ops::DivAssign<usize> for Mint { fn div_assign(&mut self, rhs: usize) { *self /= Mint::new(rhs as i64); } } impl<T> std::ops::Div<T> for Mint where Mint: std::ops::DivAssign<T>, { type Output = Self; fn div(self, other: T) -> Self { let mut res = self; res /= other; res } } impl std::fmt::Display for Mint { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::ops::Deref for Mint { type Target = i64; fn deref(&self) -> &Self::Target { &self.0 } } impl std::ops::DerefMut for Mint { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.0 } } struct UnionFind { n: usize, par: Vec<usize>, rank: Vec<usize>, } impl UnionFind { fn new(n: usize) -> Self { UnionFind { n, par: (0..n).collect(), rank: vec![1; n], } } fn unite(&mut self, x: usize, y: usize) { let rx = self.root(x); let ry = self.root(y); if rx == ry { return; } if self.rank[x] > self.rank[y] { self.par[ry] = rx; self.rank[rx] += self.rank[ry]; } else { self.par[rx] = ry; self.rank[ry] += self.rank[rx]; } } fn same(&mut self, x: usize, y: usize) -> bool { self.root(x) == self.root(y) } fn root(&mut self, x: usize) -> usize { if self.par[x] == x { x } else { self.par[x] = self.root(self.par[x]); self.par[x] } } fn size(&mut self, x: usize) -> usize { let r = self.root(x); self.rank[r] } fn sizes(&mut self) -> Vec<usize> { let mut s = vec![]; for x in 0..self.n { if x == self.root(x) { s.push(self.rank[x]); } } s } } fn main() { let (n, m, r) = read!(usize, usize, i64); let r = mint!(r); let mut uf = UnionFind::new(n); let mut to = vec![vec![]; n]; let mut i = 0; for (x, y, z) in (0..m).map(|_| read!(usize1, usize1, usize)) { if uf.same(x, y) { continue; } uf.unite(x, y); to[x].push((y, i, z)); to[y].push((x, i, z)); i += 1; } let mut cost = vec![r; i]; dfs(n, 0, None, &to, &mut cost); let mut ans = mint!(0); for c in cost { ans += c; } println!("{}", ans); } fn dfs( n: usize, u: usize, p: Option<usize>, to: &Vec<Vec<(usize, usize, usize)>>, cost: &mut Vec<Mint>, ) -> usize { let mut d = 1; for &(v, i, z) in to[u].iter() { if p == Some(v) { continue; } let m = dfs(n, v, Some(u), to, cost); cost[i] = cost[i].pow(z) * ((n - m) * m) as i64; d += m; } d }