結果
問題 | No.1023 Cyclic Tour |
ユーザー | fukafukatani |
提出日時 | 2020-04-11 11:01:59 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 114 ms / 2,000 ms |
コード長 | 3,812 bytes |
コンパイル時間 | 1,228 ms |
コンパイル使用メモリ | 186,024 KB |
実行使用メモリ | 20,856 KB |
最終ジャッジ日時 | 2023-10-18 23:19:04 |
合計ジャッジ時間 | 10,463 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 0 ms
4,348 KB |
testcase_03 | AC | 1 ms
4,348 KB |
testcase_04 | AC | 32 ms
6,428 KB |
testcase_05 | AC | 31 ms
6,436 KB |
testcase_06 | AC | 34 ms
6,660 KB |
testcase_07 | AC | 32 ms
6,520 KB |
testcase_08 | AC | 46 ms
10,136 KB |
testcase_09 | AC | 59 ms
15,468 KB |
testcase_10 | AC | 59 ms
15,504 KB |
testcase_11 | AC | 68 ms
16,276 KB |
testcase_12 | AC | 71 ms
17,844 KB |
testcase_13 | AC | 65 ms
16,920 KB |
testcase_14 | AC | 60 ms
16,708 KB |
testcase_15 | AC | 63 ms
17,168 KB |
testcase_16 | AC | 98 ms
20,696 KB |
testcase_17 | AC | 97 ms
20,856 KB |
testcase_18 | AC | 99 ms
19,736 KB |
testcase_19 | AC | 93 ms
19,712 KB |
testcase_20 | AC | 92 ms
15,760 KB |
testcase_21 | AC | 96 ms
16,068 KB |
testcase_22 | AC | 104 ms
16,940 KB |
testcase_23 | AC | 110 ms
17,300 KB |
testcase_24 | AC | 114 ms
19,872 KB |
testcase_25 | AC | 94 ms
15,812 KB |
testcase_26 | AC | 92 ms
14,780 KB |
testcase_27 | AC | 79 ms
14,072 KB |
testcase_28 | AC | 110 ms
19,000 KB |
testcase_29 | AC | 109 ms
19,752 KB |
testcase_30 | AC | 113 ms
19,500 KB |
testcase_31 | AC | 103 ms
18,384 KB |
testcase_32 | AC | 102 ms
18,916 KB |
testcase_33 | AC | 114 ms
19,004 KB |
testcase_34 | AC | 32 ms
7,736 KB |
testcase_35 | AC | 68 ms
8,992 KB |
testcase_36 | AC | 100 ms
16,176 KB |
testcase_37 | AC | 101 ms
17,988 KB |
testcase_38 | AC | 106 ms
18,968 KB |
testcase_39 | AC | 109 ms
17,400 KB |
testcase_40 | AC | 105 ms
17,716 KB |
testcase_41 | AC | 104 ms
17,596 KB |
testcase_42 | AC | 85 ms
9,960 KB |
testcase_43 | AC | 84 ms
12,160 KB |
testcase_44 | AC | 39 ms
10,440 KB |
testcase_45 | AC | 83 ms
20,456 KB |
testcase_46 | AC | 56 ms
19,372 KB |
testcase_47 | AC | 36 ms
9,848 KB |
testcase_48 | AC | 91 ms
16,976 KB |
testcase_49 | AC | 81 ms
15,472 KB |
testcase_50 | AC | 93 ms
16,956 KB |
testcase_51 | AC | 77 ms
11,832 KB |
testcase_52 | AC | 78 ms
11,572 KB |
コンパイルメッセージ
warning: unused variable: `i` --> Main.rs:29:9 | 29 | for i in 0..m { | ^ help: if this is intentional, prefix it with an underscore: `_i` | = note: `#[warn(unused_variables)]` on by default warning: method `get_size` is never used --> Main.rs:102:8 | 79 | impl UnionFindTree { | ------------------ method in this implementation ... 102 | fn get_size(&mut self, x: usize) -> usize { | ^^^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: 2 warnings emitted
ソースコード
#![allow(unused_imports)] #![allow(non_snake_case)] use std::cmp::*; use std::collections::*; use std::io::Write; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn yes() { println!("Yes"); std::process::exit(0); } fn main() { let v = read_vec::<usize>(); let (n, m) = (v[0], v[1]); let mut graph = vec![vec![]; n]; let mut uft = UnionFindTree::new(n); for i in 0..m { let v = read_vec::<usize>(); let (a, b, c) = (v[0] - 1, v[1] - 1, v[2]); if c == 1 { if uft.same(a, b) { yes(); } uft.unite(a, b); } else { graph[a].push(b); } } let mut edges = vec![]; for i in 0..n { for &to in graph[i].iter() { if uft.same(i, to) { yes(); } edges.push((uft.find(i), uft.find(to))); } } if let Some(_) = topological_sort(&edges, n) { println!("No"); return; } yes(); } fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[derive(Debug, Clone)] struct UnionFindTree { parent: Vec<isize>, size: Vec<usize>, height: Vec<u64>, } impl UnionFindTree { fn new(n: usize) -> UnionFindTree { UnionFindTree { parent: vec![-1; n], size: vec![1usize; n], height: vec![0u64; n], } } fn find(&mut self, index: usize) -> usize { if self.parent[index] == -1 { return index; } let idx = self.parent[index] as usize; let ret = self.find(idx); self.parent[index] = ret as isize; ret } fn same(&mut self, x: usize, y: usize) -> bool { self.find(x) == self.find(y) } fn get_size(&mut self, x: usize) -> usize { let idx = self.find(x); self.size[idx] } fn unite(&mut self, index0: usize, index1: usize) -> bool { let a = self.find(index0); let b = self.find(index1); if a == b { false } else { if self.height[a] > self.height[b] { self.parent[b] = a as isize; self.size[a] += self.size[b]; } else if self.height[a] < self.height[b] { self.parent[a] = b as isize; self.size[b] += self.size[a]; } else { self.parent[b] = a as isize; self.size[a] += self.size[b]; self.height[a] += 1; } true } } } fn topological_sort(edges: &Vec<(usize, usize)>, v: usize) -> Option<Vec<usize>> { let mut h = vec![0; v]; let mut g = vec![Vec::new(); v]; for &(s, t) in edges { g[s].push(t); h[t] += 1; } let mut st: std::collections::VecDeque<usize> = std::collections::VecDeque::new(); for i in 0..v { if h[i] == 0 { st.push_back(i); } } let mut sorted_indexes = Vec::new(); while !st.is_empty() { let i = st.pop_back().unwrap(); sorted_indexes.push(i); for &j in g[i].iter() { h[j] -= 1; if h[j] == 0 { st.push_back(j); } } } debug!(sorted_indexes); if sorted_indexes.len() == v { Some(sorted_indexes) } else { None } }