Submission #7664894
Source Code Expand
// ${url}
//
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;
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_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_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, [ next / $t:tt ]) => {
{
let len = read_value!($iter, usize);
(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")
};
}
#[allow(unused_macros)]
macro_rules! dvec {
($t:expr ; $len:expr) => {
vec![$t; $len]
};
($t:expr ; $len:expr, $($rest:expr),*) => {
vec![dvec!($t; $($rest),*); $len]
};
}
#[allow(unused_macros)]
macro_rules! ifv {
($t:expr, $a:expr, $b: expr) => {
if $t { $a } else { $b }
}
}
#[allow(unused_macros)]
macro_rules! fill {
($t:expr, $v:expr) => {
for i in 0..$t.len() {
$t[i] = $v;
}
};
}
#[allow(unused_macros)]
macro_rules! debug {
($($a:expr),*) => {
println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
}
}
#[derive(Debug, Clone, PartialEq)]
struct State {
is_white: bool,
children: usize,
best: (i64, i64),
value: Vec<i64> // value[0] = back, value[1] = go
}
fn add(now: usize, child: usize, states: &mut Vec<State>) {
let back = states[child].value[2];
let go = states[child].value[3];
if back == -1 {
return;
}
let back_dgo = back - go;
let (mut one, mut two) = states[now].best;
if one < back_dgo {
two = one;
one = back_dgo;
} else if two < back_dgo {
two = back_dgo;
}
states[now].children += 1;
states[now].value[0] += back + 2;
states[now].value[1] = states[now].value[0] - one - 1;
let add = ifv!(((states[now].children + 1) % 2 == 1) ^ states[now].is_white, 1, 0);
states[now].value[2] = states[now].value[0] + add;
states[now].value[3] = states[now].value[1] + (add ^ 1);
states[now].best = (one, two);
}
fn remove(now: usize, child: usize, states: &mut Vec<State>) {
let back = states[child].value[2];
let go = states[child].value[3];
if back == -1 {
return;
}
let back_dgo = back - go;
let (one, two) = states[now].best;
states[now].children -= 1;
states[now].value[0] -= back + 2;
states[now].value[1] = states[now].value[0] - ifv!(one == back_dgo, two, one) - 1;
let add = ifv!(((states[now].children + 1) % 2 == 1) ^ states[now].is_white, 1, 0);
states[now].value[2] = states[now].value[0] + add;
states[now].value[3] = states[now].value[1] + (add ^ 1);
states[now].best = ifv!(one == back_dgo, (two, 0), ifv!(two == back_dgo, (one, 0), (one, two)));
if states[now].children == 0 {
if states[now].is_white {
states[now].value[0] = 0;
states[now].value[1] = 0;
states[now].value[2] = 0;
states[now].value[3] = 0;
states[now].best = (0, 0);
} else {
states[now].value[0] = 0;
states[now].value[1] = 0;
states[now].value[2] = -1;
states[now].value[3] = -1;
states[now].best = (0, 0);
}
}
}
fn dfs(now: usize, par: Option<usize>, graph: &Vec<Vec<usize>>, states: &mut Vec<State>) {
for &to in &graph[now] {
if Some(to) == par {
continue;
}
dfs(to, Some(now), graph, states);
add(now, to, states);
}
}
fn dfs2(now: usize, par: Option<usize>, graph: &Vec<Vec<usize>>, states: &mut Vec<State>) -> i64 {
let mut best = states[now].value[1];
if states[now].children == 0 {
best += ifv!(states[now].is_white, 1, 0);
} else {
let flip = (states[now].children - 1) % 2;
best += ifv!(states[now].is_white ^ (flip == 1), 1, 0);
}
let ws = states[now].value.clone();
// debug!(now, best);
// debug!(now, states[now]);
for &to in &graph[now] {
if Some(to) == par {
continue;
}
remove(now, to, states);
add(to, now, states);
best = min(best, dfs2(to, Some(now), graph, states));
remove(to, now, states);
add(now, to, states);
}
assert_eq!(states[now].value, ws);
// debug!(now, states[now]);
best
}
fn main() {
input! {
n: usize,
edges: [(usize1, usize1); n-1],
color: chars
};
let mut graph = vec![vec![]; n];
for (u, v) in edges {
graph[u].push(v);
graph[v].push(u);
}
for i in 0..1 {
let mut states = vec![];
for i in 0..n {
let w = ifv!(color[i] == 'B', -1, 0);
states.push(State {
is_white: color[i] == 'W',
children: 0,
best: (0, 0),
value: vec![0, 0, w, w],
});
}
dfs(i, None, &graph, &mut states);
let ans = dfs2(i, None, &graph, &mut states);
println!("{}", ans);
}
// println!("{:?}", states);
}
Submission Info
Submission Time |
|
Task |
F - Monochrome Cat |
User |
hamadu |
Language |
Rust (1.15.1) |
Score |
800 |
Code Size |
6312 Byte |
Status |
AC |
Exec Time |
99 ms |
Memory |
47968 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
800 / 800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt, 1_064.txt, 1_065.txt, 1_066.txt, 1_067.txt, 1_068.txt, 1_069.txt, 1_070.txt, 1_071.txt, 1_072.txt, 1_073.txt, 1_074.txt, 1_075.txt, 1_076.txt, 1_077.txt, 1_078.txt, 1_079.txt, 1_080.txt, 1_081.txt, 1_082.txt, 1_083.txt, 1_084.txt, 1_085.txt, 1_086.txt, 1_087.txt, 1_088.txt, 1_089.txt, 1_090.txt, 1_091.txt, 1_092.txt, 1_093.txt, 1_094.txt, 1_095.txt, 1_096.txt, 1_097.txt, 1_098.txt, 1_099.txt, 1_100.txt, 1_101.txt, 1_102.txt, 1_103.txt, 1_104.txt, 1_105.txt, 1_106.txt, 1_107.txt, 1_108.txt, 1_109.txt, 1_110.txt, 1_111.txt, 1_112.txt, 1_113.txt, 1_114.txt, 1_115.txt, 1_116.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
2 ms |
4352 KB |
0_001.txt |
AC |
2 ms |
4352 KB |
0_002.txt |
AC |
2 ms |
4352 KB |
0_003.txt |
AC |
2 ms |
4352 KB |
1_003.txt |
AC |
2 ms |
4352 KB |
1_004.txt |
AC |
2 ms |
4352 KB |
1_005.txt |
AC |
2 ms |
4352 KB |
1_006.txt |
AC |
2 ms |
4352 KB |
1_007.txt |
AC |
2 ms |
4352 KB |
1_008.txt |
AC |
2 ms |
4352 KB |
1_009.txt |
AC |
2 ms |
4352 KB |
1_010.txt |
AC |
2 ms |
4352 KB |
1_011.txt |
AC |
2 ms |
4352 KB |
1_012.txt |
AC |
2 ms |
4352 KB |
1_013.txt |
AC |
2 ms |
4352 KB |
1_014.txt |
AC |
2 ms |
4352 KB |
1_015.txt |
AC |
2 ms |
4352 KB |
1_016.txt |
AC |
2 ms |
4352 KB |
1_017.txt |
AC |
2 ms |
4352 KB |
1_018.txt |
AC |
2 ms |
4352 KB |
1_019.txt |
AC |
2 ms |
4352 KB |
1_020.txt |
AC |
2 ms |
4352 KB |
1_021.txt |
AC |
2 ms |
4352 KB |
1_022.txt |
AC |
2 ms |
4352 KB |
1_023.txt |
AC |
2 ms |
4352 KB |
1_024.txt |
AC |
2 ms |
4352 KB |
1_025.txt |
AC |
2 ms |
4352 KB |
1_026.txt |
AC |
2 ms |
4352 KB |
1_027.txt |
AC |
2 ms |
4352 KB |
1_028.txt |
AC |
2 ms |
4352 KB |
1_029.txt |
AC |
2 ms |
4352 KB |
1_030.txt |
AC |
2 ms |
4352 KB |
1_031.txt |
AC |
2 ms |
4352 KB |
1_032.txt |
AC |
2 ms |
4352 KB |
1_033.txt |
AC |
2 ms |
4352 KB |
1_034.txt |
AC |
2 ms |
4352 KB |
1_035.txt |
AC |
2 ms |
4352 KB |
1_036.txt |
AC |
2 ms |
4352 KB |
1_037.txt |
AC |
2 ms |
4352 KB |
1_038.txt |
AC |
2 ms |
4352 KB |
1_039.txt |
AC |
2 ms |
4352 KB |
1_040.txt |
AC |
2 ms |
4352 KB |
1_041.txt |
AC |
2 ms |
4352 KB |
1_042.txt |
AC |
2 ms |
4352 KB |
1_043.txt |
AC |
2 ms |
4352 KB |
1_044.txt |
AC |
2 ms |
4352 KB |
1_045.txt |
AC |
24 ms |
15428 KB |
1_046.txt |
AC |
31 ms |
24364 KB |
1_047.txt |
AC |
71 ms |
40752 KB |
1_048.txt |
AC |
58 ms |
33780 KB |
1_049.txt |
AC |
60 ms |
26868 KB |
1_050.txt |
AC |
49 ms |
27644 KB |
1_051.txt |
AC |
36 ms |
21192 KB |
1_052.txt |
AC |
10 ms |
8444 KB |
1_053.txt |
AC |
36 ms |
22776 KB |
1_054.txt |
AC |
16 ms |
12540 KB |
1_055.txt |
AC |
40 ms |
21212 KB |
1_056.txt |
AC |
20 ms |
14300 KB |
1_057.txt |
AC |
2 ms |
4476 KB |
1_058.txt |
AC |
28 ms |
17528 KB |
1_059.txt |
AC |
19 ms |
12468 KB |
1_060.txt |
AC |
42 ms |
20340 KB |
1_061.txt |
AC |
53 ms |
25776 KB |
1_062.txt |
AC |
27 ms |
18680 KB |
1_063.txt |
AC |
28 ms |
14588 KB |
1_064.txt |
AC |
22 ms |
13688 KB |
1_065.txt |
AC |
4 ms |
6396 KB |
1_066.txt |
AC |
36 ms |
20756 KB |
1_067.txt |
AC |
10 ms |
8444 KB |
1_068.txt |
AC |
24 ms |
14520 KB |
1_069.txt |
AC |
14 ms |
8444 KB |
1_070.txt |
AC |
24 ms |
13944 KB |
1_071.txt |
AC |
39 ms |
21684 KB |
1_072.txt |
AC |
26 ms |
14288 KB |
1_073.txt |
AC |
6 ms |
6396 KB |
1_074.txt |
AC |
4 ms |
6396 KB |
1_075.txt |
AC |
23 ms |
13420 KB |
1_076.txt |
AC |
51 ms |
24252 KB |
1_077.txt |
AC |
36 ms |
20600 KB |
1_078.txt |
AC |
15 ms |
8444 KB |
1_079.txt |
AC |
23 ms |
13356 KB |
1_080.txt |
AC |
24 ms |
14072 KB |
1_081.txt |
AC |
89 ms |
37472 KB |
1_082.txt |
AC |
77 ms |
38368 KB |
1_083.txt |
AC |
77 ms |
47968 KB |
1_084.txt |
AC |
79 ms |
38752 KB |
1_085.txt |
AC |
90 ms |
44640 KB |
1_086.txt |
AC |
99 ms |
45664 KB |
1_087.txt |
AC |
47 ms |
24808 KB |
1_088.txt |
AC |
47 ms |
24808 KB |
1_089.txt |
AC |
39 ms |
24808 KB |
1_090.txt |
AC |
42 ms |
24808 KB |
1_091.txt |
AC |
57 ms |
24808 KB |
1_092.txt |
AC |
55 ms |
24808 KB |
1_093.txt |
AC |
65 ms |
29444 KB |
1_094.txt |
AC |
64 ms |
36100 KB |
1_095.txt |
AC |
60 ms |
31108 KB |
1_096.txt |
AC |
61 ms |
35460 KB |
1_097.txt |
AC |
61 ms |
31616 KB |
1_098.txt |
AC |
64 ms |
34820 KB |
1_099.txt |
AC |
61 ms |
24812 KB |
1_100.txt |
AC |
52 ms |
24816 KB |
1_101.txt |
AC |
43 ms |
24812 KB |
1_102.txt |
AC |
47 ms |
24812 KB |
1_103.txt |
AC |
52 ms |
24812 KB |
1_104.txt |
AC |
49 ms |
24812 KB |
1_105.txt |
AC |
57 ms |
24328 KB |
1_106.txt |
AC |
55 ms |
24324 KB |
1_107.txt |
AC |
52 ms |
24328 KB |
1_108.txt |
AC |
48 ms |
24328 KB |
1_109.txt |
AC |
54 ms |
24460 KB |
1_110.txt |
AC |
51 ms |
24332 KB |
1_111.txt |
AC |
54 ms |
24332 KB |
1_112.txt |
AC |
55 ms |
24332 KB |
1_113.txt |
AC |
45 ms |
24332 KB |
1_114.txt |
AC |
64 ms |
24328 KB |
1_115.txt |
AC |
53 ms |
24328 KB |
1_116.txt |
AC |
50 ms |
24328 KB |