CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:drvilepis
Submission time:2022-10-31 12:40:57 +0200
Language:Rust
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2details
#2ACCEPTED0.00 s1, 2details
#3ACCEPTED0.00 s1, 2details
#4ACCEPTED0.00 s1, 2details
#5ACCEPTED0.00 s1, 2details
#6ACCEPTED0.11 s1, 2details
#7--2details
#8ACCEPTED0.00 s1, 2details
#9--2details
#10ACCEPTED0.00 s1, 2details
#11ACCEPTED0.16 s2details
#12--2details
#13ACCEPTED0.25 s2details
#14ACCEPTED0.13 s2details
#150.01 s1, 2details
#16ACCEPTED0.00 s1, 2details
#17ACCEPTED0.00 s1, 2details
#18ACCEPTED0.01 s1, 2details
#19ACCEPTED0.00 s1, 2details
#20ACCEPTED0.00 s1, 2details
#21--2details
#22ACCEPTED0.14 s2details
#23ACCEPTED0.30 s2details
#24ACCEPTED0.01 s1, 2details
#25--2details
#26ACCEPTED0.01 s1, 2details
#27--2details
#28ACCEPTED0.01 s1, 2details
#29--2details
#30ACCEPTED0.02 s1, 2details
#31--2details

Compiler report

warning: value assigned to `cur` is never read
  --> input/code.rs:65:17
   |
65 |         let mut cur: Vec<(usize, Option<usize>, usize)> = vec![];
   |                 ^^^
   |
   = note: `#[warn(unused_assignments)]` on by default
   = help: maybe it is overwritten before being read?

warning: unused variable: `n_cities`
  --> input/code.rs:17:9
   |
17 |     let n_cities = input.trim().parse::<usize>().unwrap();
   |         ^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_n_cities`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused `Result` that must be used
  --> input/code.rs:16:5
   |
16 |     stdin.read_line(&mut input);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: `#[warn(unused_must_use)]` on by default
   = note: this `Result` may be an `Err` variant, which should be handled

warning: unused `Result` that must be used
  --> input/code.rs:20:5
   |
20 |     stdin.read_line(&mut input);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^...

Code

use std::collections::HashMap;

fn sort(i: usize, j: usize) -> (usize, usize) {
    if i < j {
        (i, j)
    } else {
        (j, i)
    }
}

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

    let mut input = String::new();

    stdin.read_line(&mut input);
    let n_cities = input.trim().parse::<usize>().unwrap();
    input.clear();

    stdin.read_line(&mut input);

    // true on satama, false on pelto
    let types = input.split_whitespace().map(|c| c.chars().next().unwrap() == '0').collect::<Vec<_>>();
    input.clear();

    let mut lenmap = HashMap::new();
    let mut bridgemap: HashMap<usize, Vec<usize>> = HashMap::new();

    loop {
        let res = stdin.read_line(&mut input);

        if let Ok(0) = res {
            break;
        };

        let mut nums = input.split_whitespace().map(|c| c.parse::<usize>().unwrap());
        let (i, j) = (nums.next().unwrap() - 1, nums.next().unwrap() - 1);

        let (i, j) = sort(i, j);

        lenmap.insert((i, j), nums.next().unwrap());

        if let Some(vec) = bridgemap.get_mut(&i) {
            vec.push(j)
        } else {
            bridgemap.insert(i, vec![j]);
        }

        if let Some(vec) = bridgemap.get_mut(&j) {
            vec.push(i)
        } else {
            bridgemap.insert(j, vec![i]);
        }

        input.clear();
    }

    let sum = types.iter().enumerate().filter_map(|(i, &t)| {
        if t {
            return None;
        }

        let mut min_dist: Option<usize> = None;

        let mut cur: Vec<(usize, Option<usize>, usize)> = vec![];
        let mut last: Vec<(usize, Option<usize>, usize)> = vec![];

        last.push((i, None, 0));

        for _ in 1..20 {
            cur = last.iter().map(|&(cur_node, last_node_opt, length)| {
                let mut other_nodes = bridgemap.get(&cur_node).unwrap().clone();
                if let Some(last_node) = last_node_opt {
                    let index = other_nodes.iter().position(|&node| node == last_node).unwrap();
                    other_nodes.remove(index);
                };

                let mut out = vec![];

                for other_node in other_nodes {
                    let new_length = length + *lenmap.get(&sort(other_node, cur_node)).unwrap();

                    if let Some(dist) = min_dist {
                        if new_length >= dist {
                            continue
                        };
                    };

                    if !types[other_node] {
                        out.push((other_node, Some(cur_node), new_length));
                    } else {
                        if let Some(dist) = min_dist {
                            if new_length < dist {
                                min_dist = Some(new_length);
                            }
                        } else {
                            min_dist = Some(new_length);
                        }
                    }
                }

                out
            }).flatten().collect();

            last = cur.clone();
            cur.clear();
        }

        min_dist
    }).sum::<usize>();

    println!("{}", sum);
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
1
0

correct output
0

user output
0

Test 2

Group: 1, 2

Verdict: ACCEPTED

input
5
0 0 0 0 0
1 2 1
2 3 2
3 4 3
...

correct output
0

user output
0

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
4
1 0 1 1
1 2 10
2 3 20
2 4 30

correct output
60

user output
60

Test 4

Group: 1, 2

Verdict: ACCEPTED

input
5
0 1 1 1 0
1 2 10
2 3 20
3 4 30
...

correct output
80

user output
80

Test 5

Group: 1, 2

Verdict: ACCEPTED

input
5
0 1 0 1 1
1 2 1
2 3 5
3 4 3
...

correct output
6

user output
6

Test 6

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5506363

user output
5506363

Test 7

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1795118520

user output
(empty)

Test 8

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 ...

correct output
293576

user output
293576

Test 9

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
816932444

user output
(empty)

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
3089

user output
3089

Test 11

Group: 2

Verdict: ACCEPTED

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
40839

user output
40839

Test 12

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5683983203973

user output
(empty)

Test 13

Group: 2

Verdict: ACCEPTED

input
200000
0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 ...

correct output
58572993

user output
58572993

Test 14

Group: 2

Verdict: ACCEPTED

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
32755

user output
32755

Test 15

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
126238345

user output
180285

Test 16

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 ...

correct output
278678

user output
278678

Test 17

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 ...

correct output
34929

user output
34929

Test 18

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1543963

user output
1543963

Test 19

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
39606

user output
39606

Test 20

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 ...

correct output
321598

user output
321598

Test 21

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
978670626

user output
(empty)

Test 22

Group: 2

Verdict: ACCEPTED

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
375218

user output
375218

Test 23

Group: 2

Verdict: ACCEPTED

input
200000
1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 ...

correct output
60422556

user output
60422556

Test 24

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
291990

user output
291990

Test 25

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
59607954

user output
(empty)

Test 26

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
990

user output
990

Test 27

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
199982

user output
(empty)

Test 28

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
7987

user output
7987

Test 29

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
3137875

user output
(empty)

Test 30

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
4657693

user output
4657693

Test 31

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1652889357

user output
(empty)