Submission #1435145
Source Code Expand
fn dfs(u: usize, p: usize, depth: &mut Vec<usize>, parent: &mut Vec<usize>, next: &Vec<Vec<usize>>) {
for &v in &next[u] {
if v != p {
depth[v] = depth[u] + 1;
parent[v] = u;
dfs(v, u, depth, parent, next);
}
}
}
fn cnt(u: usize, p: usize, next: &Vec<Vec<usize>>) -> usize {
next[u].iter().filter(|&v| *v != p).map(|&v| cnt(v, u, next)).sum::<usize>() + 1
}
fn main() {
let n: usize = readln();
let ps: Vec<(usize, usize)> = readlns(n-1);
let mut next: Vec<Vec<usize>> = vec![vec![]; n];
for (a, b) in ps {
next[a-1].push(b-1);
next[b-1].push(a-1);
}
let mut parent: Vec<usize> = vec![0; n];
let mut depth: Vec<usize> = vec![0; n];
parent[0] = 0;
depth[0] = 0;
dfs(0, 0, &mut depth, &mut parent, &next);
let c = (depth[n-1] - 1) / 2;
let mut root = n-1;
for i in 0..c {
root = parent[root];
}
let b = cnt(root, parent[root], &next);
let a = n - b;
println!("{}", if a <= b { "Snuke" } else { "Fennec" });
}
// --- template ---
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::HashSet;
pub trait FromLn {
fn fromln(s: &str) -> Self;
}
pub fn readln<T: FromLn>() -> T {
let mut buf = String::new();
let _ = ::std::io::stdin().read_line(&mut buf).unwrap();
T::fromln(buf.trim())
}
pub fn readlns<T: FromLn>(n: usize) -> Vec<T> {
let mut vs = vec![];
for _ in 0..n { vs.push(readln()); }
vs
}
macro_rules! fromln_primitives {
($($t:ty),*) => { $(
impl FromLn for $t {
fn fromln(s: &str) -> $t {
s.parse().unwrap()
}
}
)* }
}
fromln_primitives!(String, bool, f32, f64, isize, i8, i16, i32, i64, usize, u8, u16, u32, u64);
impl<T> FromLn for Vec<T> where T: FromLn {
fn fromln(s: &str) -> Vec<T> {
s.split_whitespace().map(T::fromln).collect()
}
}
impl FromLn for Vec<char> {
fn fromln(s: &str) -> Vec<char> {
s.chars().collect()
}
}
macro_rules! fromln_tuple {
($($t:ident),*) => {
impl<$($t),*> FromLn for ($($t),*) where $($t: FromLn),* {
fn fromln(s: &str) -> ($($t),*) {
let mut it = s.split_whitespace();
let t = ($($t::fromln(it.next().unwrap())),*);
assert_eq!(it.next(), None);
t
}
}
}
}
fromln_tuple!(A, B);
fromln_tuple!(A, B, C);
fromln_tuple!(A, B, C, D);
fromln_tuple!(A, B, C, D, E);
fromln_tuple!(A, B, C, D, E, F);
Submission Info
Submission Time |
|
Task |
D - Fennec VS. Snuke |
User |
ichyo |
Language |
Rust (1.15.1) |
Score |
400 |
Code Size |
2660 Byte |
Status |
AC |
Exec Time |
41 ms |
Memory |
18684 KB |
Compile Error
warning: unused variable: `i`, #[warn(unused_variables)] on by default
--> ./Main.rs:28:9
|
28 | for i in 0..c {
| ^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt |
All |
00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
2 ms |
4352 KB |
00_example_02.txt |
AC |
2 ms |
4352 KB |
01.txt |
AC |
2 ms |
4352 KB |
02.txt |
AC |
2 ms |
4352 KB |
03.txt |
AC |
2 ms |
4352 KB |
04.txt |
AC |
2 ms |
4352 KB |
05.txt |
AC |
32 ms |
12156 KB |
06.txt |
AC |
36 ms |
14204 KB |
07.txt |
AC |
33 ms |
12028 KB |
08.txt |
AC |
35 ms |
14076 KB |
09.txt |
AC |
2 ms |
4352 KB |
10.txt |
AC |
32 ms |
10492 KB |
11.txt |
AC |
34 ms |
12540 KB |
12.txt |
AC |
35 ms |
12540 KB |
13.txt |
AC |
36 ms |
12540 KB |
14.txt |
AC |
35 ms |
12540 KB |
15.txt |
AC |
35 ms |
12540 KB |
16.txt |
AC |
40 ms |
18684 KB |
17.txt |
AC |
40 ms |
18684 KB |
18.txt |
AC |
41 ms |
18684 KB |
19.txt |
AC |
41 ms |
18684 KB |