CSES - Datatähti 2023 alku - Results
Submission details
Task:Ruudukko
Sender:drvilepis
Submission time:2022-11-03 16:21:12 +0200
Language:Rust
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.00 s1, 2, 3details
#20.00 s1, 2, 3details
#30.00 s1, 2, 3details
#40.00 s2, 3details
#50.00 s2, 3details
#60.00 s2, 3details
#70.00 s3details
#80.01 s3details
#90.01 s3details

Compiler report

warning: unused variable: `min_dists`
  --> input/code.rs:83:13
   |
83 |     let mut min_dists = vec![0usize; n_cities];
   |             ^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_min_dists`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
  --> input/code.rs:83:9
   |
83 |     let mut min_dists = vec![0usize; n_cities];
   |         ----^^^^^^^^^
   |         |
   |         help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: 2 warnings emitted

Code

use std::collections::HashMap;
#[derive(Eq)]
struct Path {
cur_node: usize,
last_node: Option<usize>,
length: usize,
}
impl Ord for Path {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.length.cmp(&other.length).reverse()
}
}
impl PartialOrd for Path {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.length.cmp(&other.length))
}
}
impl PartialEq for Path {
fn eq(&self, other: &Self) -> bool {
self.length.eq(&other.length)
}
}
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).unwrap();
let n_cities = input.trim().parse::<usize>().unwrap();
input.clear();
stdin.read_line(&mut input).unwrap();
// 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).unwrap();
if res == 0 {
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 mut min_dists = vec![0usize; n_cities];
let sum = types.iter().enumerate().filter_map(|(i, &t)| {
if !t {
return None;
}
let mut min_dist: Option<usize> = None;
let mut nums: Vec<Path> = vec![];
nums.push(Path {
cur_node: i,
last_node: None,
length: 0
});
loop {
nums = nums.iter().map(|path| {
if let Some(dist) = min_dist {
if path.length > dist {
return vec![];
}
}
let other_nodes = bridgemap.get(&path.cur_node).unwrap().clone();
let mut out = vec![];
for other_node in other_nodes {
if let Some(last_node) = path.last_node {
if other_node == last_node {
continue;
}
};
let new_length = path.length + *lenmap.get(&sort(other_node, path.cur_node)).unwrap();
if let Some(dist) = min_dist {
if new_length >= dist {
continue
};
};
if !types[other_node] {
out.push(Path {
cur_node: other_node,
last_node: Some(path.cur_node),
length: 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();
if nums.is_empty() {
break;
}
}
min_dist
}).sum::<usize>();
println!("{}", sum);
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
3
1 1 1
1 1 1
1 1 1

correct output
9

user output
0

Test 2

Group: 1, 2, 3

Verdict:

input
3
1 2 3
6 5 4
7 8 9

correct output
135

user output
0

Test 3

Group: 1, 2, 3

Verdict:

input
3
7 8 1
4 5 4
3 9 6

correct output
57

user output
0

Test 4

Group: 2, 3

Verdict:

input
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
10000

user output
0

Test 5

Group: 2, 3

Verdict:

input
100
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
187458477

user output
0

Test 6

Group: 2, 3

Verdict:

input
100
2995 8734 1018 2513 7971 5063 ...

correct output
964692694

user output
0

Test 7

Group: 3

Verdict:

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

correct output
1000000

user output
0

Test 8

Group: 3

Verdict:

input
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
229147081

user output
0

Test 9

Group: 3

Verdict:

input
1000
520283 805991 492643 75254 527...

correct output
951147313

user output
0