CSES - Datatähti 2024 alku - Results
Submission details
Task:Laskettelukeskus
Sender:EmuBird
Submission time:2023-10-31 15:58:28 +0200
Language:Rust
Status:READY
Result:53
Feedback
groupverdictscore
#1ACCEPTED53
#20
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2details
#2ACCEPTED0.00 s1, 2details
#3ACCEPTED0.00 s1, 2details
#40.17 s2details
#50.17 s2details
#6ACCEPTED0.00 s1, 2details
#7ACCEPTED0.16 s2details
#8ACCEPTED0.00 s1, 2details
#9ACCEPTED0.13 s2details
#10ACCEPTED0.00 s1, 2details
#110.14 s2details
#12ACCEPTED0.00 s1, 2details
#130.14 s2details

Compiler report

warning: variable does not need to be mutable
  --> input/code.rs:63:9
   |
63 |     let mut depth_map: Vec<HashSet<usize>> = {
   |         ----^^^^^^^^^
   |         |
   |         help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: 1 warning emitted

Code

use std::cmp::max;
use std::collections::{HashMap, HashSet};
use std::io;

fn main() {
    let stdin = io::stdin();

    let slope_count = { // AKA n
        let 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 times
        for _ 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::<u32>().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 mut 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 processed
        let 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: u32, // number of required plows,
    child_plows: u32 // 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:

input
100000
1 45452
1 74209
45452 78960
45452 79820
...

correct output
28399367694319

user output
2392863168

Test 5

Group: 2

Verdict:

input
100000
1 31165
1 23263
31165 89516
31165 53122
...

correct output
28546840313799

user output
3846274095

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:

input
100000
1 2
1 3
2 4
2 5
...

correct output
26053917212428

user output
1404255480

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:

input
100000
1 2
1 3
2 4
2 5
...

correct output
50000000000000

user output
3747910656