Task: | Laskettelukeskus |
Sender: | EmuBird |
Submission time: | 2023-10-31 17:06:42 +0200 |
Language: | Rust |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 53 |
#2 | ACCEPTED | 47 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | ACCEPTED | 0.00 s | 1, 2 | details |
#3 | ACCEPTED | 0.00 s | 1, 2 | details |
#4 | ACCEPTED | 0.17 s | 2 | details |
#5 | ACCEPTED | 0.19 s | 2 | details |
#6 | ACCEPTED | 0.00 s | 1, 2 | details |
#7 | ACCEPTED | 0.16 s | 2 | details |
#8 | ACCEPTED | 0.00 s | 1, 2 | details |
#9 | ACCEPTED | 0.12 s | 2 | details |
#10 | ACCEPTED | 0.00 s | 1, 2 | details |
#11 | ACCEPTED | 0.14 s | 2 | details |
#12 | ACCEPTED | 0.00 s | 1, 2 | details |
#13 | ACCEPTED | 0.14 s | 2 | details |
Code
use std::cmp::max;use std::collections::{HashMap, HashSet};use std::io;fn main() {let stdin = io::stdin();let slope_count = { // AKA nlet mut input: String = String::new();stdin.read_line(&mut input).unwrap();input.replace("\r", "").replace("\n", "").parse::<usize>().unwrap()};// All slopes indexed by their IDs.let mut slopes = {let mut slopes: Vec<SkiSlope> = Vec::with_capacity(slope_count);for _ in 0..slope_count {slopes.push(SkiSlope {upward_connections: HashSet::new(),downward_connections: HashSet::new(),plows: 0, // Will be initialized later.child_plows: 0 // Will be initialized later.});}slopes};// Read routes{// Read line slope_count - 1 timesfor _ in 1..slope_count {let mut input: String = String::new();stdin.read_line(&mut input).unwrap();let route: Vec<usize> = input.replace("\r", "").replace("\n", "").split_whitespace().map(|value| {value.parse::<usize>().unwrap() - 1 // Indexes are given starting from 1, so they need to be decremented}).collect();// A route exists from route[0] (upper) to route[1] (lower).slopes[route[1]].upward_connections.insert(route[0]);slopes[route[0]].downward_connections.insert(route[1]);}};// Read number of required plows.{let mut input: String = String::new();stdin.read_line(&mut input).unwrap();input.replace("\r", "").replace("\n", "").split_whitespace().enumerate().for_each(|(i, value)| {slopes[i].plows = value.parse().unwrap();});}// List of ski slopes indexed by their depth from the root slope. Depth is 0 for the root slope.// Otherwise this could be calculated while taking input, but it's possible depth would be determined before the parent's depth is calculated.let depth_map: Vec<HashSet<usize>> = {let mut depth_map: Vec<HashSet<usize>> = Vec::new();depth_map.insert(0, HashSet::from([ 0 ])); // Root slope is at depth 0.// Calculate required plows from bottom to top.// key-value pairs of slopes to be processedlet mut loop_slopes: HashMap<usize, usize> = HashMap::with_capacity(1);loop_slopes.insert(0, 0); // Adds root slope manually.while !&loop_slopes.is_empty() {let mut next_slopes = HashMap::new();for (parent_slope_id, depth) in &loop_slopes {let slope = &slopes[*parent_slope_id];let new_depth = depth + 1;if depth_map.len() >= new_depth {depth_map.push(HashSet::new());}let set = &mut depth_map[new_depth];for lower_slope_id in slope.downward_connections.clone() {set.insert(lower_slope_id);next_slopes.insert(lower_slope_id, new_depth);}}loop_slopes = next_slopes;}depth_map};// Calculate required plows in reverse depth order.for slope_ids in depth_map.iter().rev() {for slope_id in slope_ids {let slope = &mut slopes[*slope_id];slope.plows = max(slope.plows, slope.child_plows);let plows = slope.plows;for upper_slope_id in slope.upward_connections.clone() {let mut upper_slope = &mut slopes[upper_slope_id];upper_slope.child_plows += plows;}}}println!("{}", slopes[0].plows); // Print required plows for the root ski slope.}struct SkiSlope {upward_connections: HashSet<usize>,downward_connections: HashSet<usize>,plows: u64, // number of required plows,child_plows: u64 // required plows of all children combined}
Test details
Test 1
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 1 2 1 3 3 4 3 5 ... |
correct output |
---|
6 |
user output |
---|
6 |
Test 2
Group: 1, 2
Verdict: ACCEPTED
input |
---|
100 1 73 1 64 64 23 1 88 ... |
correct output |
---|
2675 |
user output |
---|
2675 |
Test 3
Group: 1, 2
Verdict: ACCEPTED
input |
---|
100 1 36 36 56 56 59 36 97 ... |
correct output |
---|
2808 |
user output |
---|
2808 |
Test 4
Group: 2
Verdict: ACCEPTED
input |
---|
100000 1 45452 1 74209 45452 78960 45452 79820 ... |
correct output |
---|
28399367694319 |
user output |
---|
28399367694319 |
Test 5
Group: 2
Verdict: ACCEPTED
input |
---|
100000 1 31165 1 23263 31165 89516 31165 53122 ... |
correct output |
---|
28546840313799 |
user output |
---|
28546840313799 |
Test 6
Group: 1, 2
Verdict: ACCEPTED
input |
---|
100 1 79 79 9 79 45 45 10 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 7
Group: 2
Verdict: ACCEPTED
input |
---|
100000 1 66038 1 56789 56789 7403 66038 69542 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 8
Group: 1, 2
Verdict: ACCEPTED
input |
---|
100 1 2 2 3 3 4 4 5 ... |
correct output |
---|
100 |
user output |
---|
100 |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
100000 1 2 2 3 3 4 4 5 ... |
correct output |
---|
1000000000 |
user output |
---|
1000000000 |
Test 10
Group: 1, 2
Verdict: ACCEPTED
input |
---|
100 1 2 1 3 2 4 2 5 ... |
correct output |
---|
2809 |
user output |
---|
2809 |
Test 11
Group: 2
Verdict: ACCEPTED
input |
---|
100000 1 2 1 3 2 4 2 5 ... |
correct output |
---|
26053917212428 |
user output |
---|
26053917212428 |
Test 12
Group: 1, 2
Verdict: ACCEPTED
input |
---|
100 1 2 1 3 2 4 2 5 ... |
correct output |
---|
5000 |
user output |
---|
5000 |
Test 13
Group: 2
Verdict: ACCEPTED
input |
---|
100000 1 2 1 3 2 4 2 5 ... |
correct output |
---|
50000000000000 |
user output |
---|
50000000000000 |