結果
問題 | No.1424 Ultrapalindrome |
ユーザー | phspls |
提出日時 | 2022-11-07 11:27:34 |
言語 | Rust (1.77.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,962 bytes |
コンパイル時間 | 1,304 ms |
コンパイル使用メモリ | 162,000 KB |
実行使用メモリ | 16,188 KB |
最終ジャッジ日時 | 2023-09-28 01:11:42 |
合計ジャッジ時間 | 5,433 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 0 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,376 KB |
testcase_09 | AC | 59 ms
11,588 KB |
testcase_10 | AC | 57 ms
11,432 KB |
testcase_11 | AC | 39 ms
8,648 KB |
testcase_12 | AC | 56 ms
10,888 KB |
testcase_13 | AC | 13 ms
4,484 KB |
testcase_14 | AC | 44 ms
9,240 KB |
testcase_15 | AC | 1 ms
4,376 KB |
testcase_16 | AC | 32 ms
7,624 KB |
testcase_17 | AC | 39 ms
8,928 KB |
testcase_18 | AC | 22 ms
6,708 KB |
testcase_19 | AC | 38 ms
8,732 KB |
testcase_20 | AC | 8 ms
4,376 KB |
testcase_21 | AC | 28 ms
7,792 KB |
testcase_22 | AC | 17 ms
5,332 KB |
testcase_23 | AC | 4 ms
4,380 KB |
testcase_24 | AC | 7 ms
4,376 KB |
testcase_25 | AC | 7 ms
4,380 KB |
testcase_26 | AC | 45 ms
10,144 KB |
testcase_27 | WA | - |
testcase_28 | AC | 35 ms
13,752 KB |
testcase_29 | AC | 35 ms
13,752 KB |
testcase_30 | AC | 42 ms
16,108 KB |
testcase_31 | AC | 43 ms
16,188 KB |
コンパイルメッセージ
warning: unused variable: `n` --> Main.rs:21:9 | 21 | let n = paths.len(); | ^ help: if this is intentional, prefix it with an underscore: `_n` | = note: `#[warn(unused_variables)]` on by default warning: 1 warning emitted
ソースコード
use std::collections::{VecDeque, HashSet}; const INF: usize = 1usize << 60; fn tree_diameter(paths: &Vec<Vec<(usize, usize)>>) -> (usize, usize, usize) { fn calc(paths: &Vec<Vec<(usize, usize)>>, start: usize) -> Vec<usize> { let n = paths.len(); let mut costs = vec![INF; n]; costs[start] = 0usize; let mut deq = VecDeque::new(); deq.push_back(start); while let Some(u) = deq.pop_front() { for &(v, cost) in paths[u].iter() { if costs[v] < INF { continue; } costs[v] = costs[v].min(costs[u] + cost); deq.push_back(v); } } costs } let n = paths.len(); let costs = calc(paths, 0); let idx = costs.into_iter().enumerate().max_by_key(|&(_, c)| c).unwrap().0; let costs = calc(paths, idx); let ridx = costs.into_iter().enumerate().max_by_key(|&(_, c)| c).unwrap(); // start_point, end_point, cost (idx, ridx.0, ridx.1) } fn get_leaves(cur: usize, paths: &Vec<Vec<(usize, usize)>>) -> Vec<bool> { let n = paths.len(); let mut ret = vec![true; n]; let mut checked = vec![false; n]; checked[cur] = true; let mut deque = VecDeque::new(); deque.push_back(cur); while let Some(u) = deque.pop_front() { for &(v, _) in paths[u].iter() { if checked[v] { continue; } checked[v] = true; ret[u] = false; deque.push_back(v); } } ret[cur] = true; ret } fn get_dists(cur: usize, paths: &Vec<Vec<(usize, usize)>>) -> Vec<usize> { let n = paths.len(); let mut ret = vec![INF; n]; ret[cur] = 0; let mut deque = VecDeque::new(); deque.push_back(cur); while let Some(u) = deque.pop_front() { for &(v, _) in paths[u].iter() { if ret[v] < INF { continue; } ret[v] = ret[u] + 1; deque.push_back(v); } } ret } fn main() { let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let mut paths = vec![vec![]; n]; for _ in 0..n-1 { let mut ab = String::new(); std::io::stdin().read_line(&mut ab).ok(); let ab: Vec<usize> = ab.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let a = ab[0]-1; let b = ab[1]-1; paths[a].push((b, 1)); paths[b].push((a, 1)); } let (left, right, _) = tree_diameter(&paths); let leaves = get_leaves(left, &paths); let l_dists = get_dists(left, &paths); let r_dists = get_dists(right, &paths); let mut result = HashSet::new(); for i in 0..n { if !leaves[i] { continue; } if i != left { result.insert(l_dists[i]); } if i != right { result.insert(r_dists[i]); } } if result.len() == 1 { println!("Yes"); } else { println!("No"); } }