Task: | Sadonkorjuu |
Sender: | drvilepis |
Submission time: | 2022-11-05 13:28:57 +0200 |
Language: | Rust |
Status: | READY |
Result: | 33 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 33 |
#2 | TIME LIMIT EXCEEDED | 0 |
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.00 s | 1, 2 | details |
#5 | ACCEPTED | 0.00 s | 1, 2 | details |
#6 | ACCEPTED | 0.12 s | 1, 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | ACCEPTED | 0.00 s | 1, 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | ACCEPTED | 0.00 s | 1, 2 | details |
#11 | ACCEPTED | 0.16 s | 2 | details |
#12 | TIME LIMIT EXCEEDED | -- | 2 | details |
#13 | ACCEPTED | 0.23 s | 2 | details |
#14 | ACCEPTED | 0.14 s | 2 | details |
#15 | ACCEPTED | 0.05 s | 1, 2 | details |
#16 | ACCEPTED | 0.00 s | 1, 2 | details |
#17 | ACCEPTED | 0.00 s | 1, 2 | details |
#18 | ACCEPTED | 0.01 s | 1, 2 | details |
#19 | ACCEPTED | 0.00 s | 1, 2 | details |
#20 | ACCEPTED | 0.00 s | 1, 2 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2 | details |
#22 | ACCEPTED | 0.14 s | 2 | details |
#23 | ACCEPTED | 0.23 s | 2 | details |
#24 | ACCEPTED | 0.00 s | 1, 2 | details |
#25 | ACCEPTED | 0.40 s | 2 | details |
#26 | ACCEPTED | 0.01 s | 1, 2 | details |
#27 | TIME LIMIT EXCEEDED | -- | 2 | details |
#28 | ACCEPTED | 0.01 s | 1, 2 | details |
#29 | TIME LIMIT EXCEEDED | -- | 2 | details |
#30 | ACCEPTED | 0.02 s | 1, 2 | details |
#31 | TIME LIMIT EXCEEDED | -- | 2 | details |
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, BinaryHeap};#[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).reverse())}}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 peltolet 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 paths = BinaryHeap::new();paths.push(Path {cur_node: i,last_node: None,length: 0});while let Some(path) = paths.pop() {if let Some(dist) = min_dist {if path.length > dist {continue;}}let other_nodes = bridgemap.get(&path.cur_node).unwrap().clone();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] {paths.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);}}}}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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
126238345 |
user output |
---|
126238345 |
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: TIME LIMIT EXCEEDED
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: ACCEPTED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
59607954 |
user output |
---|
59607954 |
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
200000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1652889357 |
user output |
---|
(empty) |