CSES - Datatähti 2020 alku - Results
Submission details
Task:Mastot
Sender:aleksih
Submission time:2019-10-10 18:43:56 +0300
Language:Rust
Status:READY
Result:45
Feedback
groupverdictscore
#1ACCEPTED11
#2ACCEPTED34
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.01 s1, 2, 3details
#11ACCEPTED0.01 s1, 2, 3details
#12ACCEPTED0.01 s1, 2, 3details
#13ACCEPTED0.01 s1, 2, 3details
#14ACCEPTED0.01 s1, 2, 3details
#15ACCEPTED0.01 s1, 2, 3details
#16ACCEPTED0.01 s1, 2, 3details
#17ACCEPTED0.01 s1, 2, 3details
#18ACCEPTED0.01 s1, 2, 3details
#19ACCEPTED0.01 s1, 2, 3details
#20ACCEPTED0.01 s1, 2, 3details
#21ACCEPTED0.01 s2, 3details
#22ACCEPTED0.01 s2, 3details
#23ACCEPTED0.01 s2, 3details
#24ACCEPTED0.01 s2, 3details
#25ACCEPTED0.01 s2, 3details
#26ACCEPTED0.01 s2, 3details
#27ACCEPTED0.01 s2, 3details
#28ACCEPTED0.01 s2, 3details
#29ACCEPTED0.01 s2, 3details
#30ACCEPTED0.01 s2, 3details
#31ACCEPTED0.01 s2, 3details
#32ACCEPTED0.01 s2, 3details
#33ACCEPTED0.01 s2, 3details
#34ACCEPTED0.02 s3details
#35ACCEPTED0.03 s3details
#36--3details
#37ACCEPTED0.03 s3details
#38ACCEPTED0.07 s3details
#39ACCEPTED0.04 s3details
#40ACCEPTED0.03 s3details
#41ACCEPTED0.03 s3details
#42ACCEPTED0.03 s3details
#43ACCEPTED0.03 s3details
#44ACCEPTED0.03 s3details
#45ACCEPTED0.03 s3details
#46ACCEPTED0.03 s3details

Code

use std::collections::BinaryHeap;

#[derive(Copy, Clone, Eq, PartialEq)]
struct Masto {
    etaisyys: usize,
    kantama: usize,
    hinta: u64,
    dijkstra_hinta: u64,
}

#[derive(Copy, Clone, Eq, PartialEq)]
struct DijkstraTila {
    hinta_yht: u64,
    paikka: usize,
}

impl std::cmp::Ord for DijkstraTila {
    fn cmp(&self, toinen: &Self) -> std::cmp::Ordering {
        toinen.hinta_yht.cmp(&self.hinta_yht)
            .then_with(|| self.paikka.cmp(&toinen.paikka))
    }
}

impl std::cmp::PartialOrd for DijkstraTila {
    fn partial_cmp(&self, toinen: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(toinen))
    }
}

fn main() {
    let mut valit_lkm_str = String::new();

    std::io::stdin().read_line(&mut valit_lkm_str).unwrap();
    let valit_lkm = valit_lkm_str.trim().parse::<usize>().unwrap();

    let mut kantamat = Vec::with_capacity(valit_lkm);
    let mut kantamat_str = String::new();
    std::io::stdin().read_line(&mut kantamat_str).unwrap();
    for luku in kantamat_str.split_ascii_whitespace() {
        kantamat.push(luku.trim().parse::<usize>().unwrap());
    }
    kantamat.push(0);

    let mut hinnat = Vec::with_capacity(valit_lkm);
    let mut hinnat_str = String::new();
    std::io::stdin().read_line(&mut hinnat_str).unwrap();
    hinnat.push(0);
    for luku in hinnat_str.split_ascii_whitespace() {
        hinnat.push(luku.trim().parse::<u64>().unwrap());
    }
    hinnat.push(0);

    let suuri_hinta = std::u64::MAX;
    let mut dijkstra_hinnat = Vec::new();
    dijkstra_hinnat.resize(valit_lkm + 1, suuri_hinta);
    dijkstra_hinnat[0] = 0;

    let mut keko = BinaryHeap::new();
    keko.push(DijkstraTila{hinta_yht: 0, paikka: 0});

    let mut summa = 0;
    while let Some(DijkstraTila{hinta_yht, paikka}) = keko.pop() {
        if kantamat[paikka] == 0 {
            summa = hinta_yht;
            break;
        }
        if hinta_yht > dijkstra_hinnat[paikka] {
            continue;
        }

        for naapuri in (paikka + 1)..std::cmp::min(hinnat.len(), paikka + kantamat[paikka] + 1) {
            let naapuri_tila = DijkstraTila{
                hinta_yht: hinta_yht + hinnat[naapuri],
                paikka: naapuri
            };
            if naapuri_tila.hinta_yht < dijkstra_hinnat[naapuri_tila.paikka] {
                keko.push(naapuri_tila);
                dijkstra_hinnat[naapuri_tila.paikka] = naapuri_tila.hinta_yht;
            }
        }
    }

    /*let suuri_hinta = 1 << 56 as u64;

    let mut dijkstra_hinnat = Vec::new();
    dijkstra_hinnat.resize(valit_lkm + 1, suuri_hinta);
    dijkstra_hinnat[0] = 0;
    let mut edellinen = Vec::new();
    edellinen.resize(valit_lkm + 1, None as Option<usize>);

    let mut mastot = BinaryHeap::new();
    for i in 0..(valit_lkm + 1) {
        mastot.push(Reverse(Masto{
            etaisyys: i,
            kantama: kantamat[i],
            hinta: hinnat[i],
            dijkstra_hinta: dijkstra_hinnat[i],
        }));
    }

    while let Some(m) = mastot.pop() {
        let masto = m.0;
        if masto.kantama == 0 {
            break;
        }
        let lahin_solu = masto.etaisyys;

        for naapuri in (lahin_solu + 1)..std::cmp::min(hinnat.len(), lahin_solu + kantamat[lahin_solu] + 1) {
            let alt = dijkstra_hinnat[lahin_solu] + hinnat[naapuri];
            if dijkstra_hinnat[lahin_solu] != suuri_hinta
                && alt < dijkstra_hinnat[naapuri] {
                dijkstra_hinnat[naapuri] = alt;
                edellinen[naapuri] = Some(lahin_solu);
            }
        }
    }

    let mut viimeinen = edellinen[valit_lkm];
    let mut summa = 0;
    loop {
        match viimeinen {
            Some(viim) => {
                summa += hinnat[viim];
                viimeinen = edellinen[viim];
            },
            None => break
        }
    }*/

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

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
6
2 2 3 1 2 4
4 1 3 4 2

correct output
3

user output
3

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
1 1
1

correct output
1

user output
1

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
2 1
1

correct output
0

user output
0

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
2 2 1
1 2

correct output
1

user output
1

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
2 2 1
2 1

correct output
1

user output
1

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
4
1 1 1 1
1000000000 1000000000 10000000...

correct output
3000000000

user output
3000000000

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
19000000000

user output
19000000000

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
1 1 2 1 1 1 2 1 1 2 1 1 1 2 1 ...

correct output
4609157377

user output
4609157377

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
20 20 20 20 20 20 20 20 20 20 ...

correct output
0

user output
0

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
19
16 10 9 17 1 16 19 4 18 13 5 3...

correct output
8424700

user output
8424700

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
2 4 3 4 4 4 4 1 1 3 4 2 1 3 3 ...

correct output
2817777553

user output
2817777553

Test 12

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
4 4 4 4 3 4 1 3 4 1 1 4 1 3 1 ...

correct output
3020673750

user output
3020673750

Test 13

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
5 1 3 4 2 4 2 2 5 1 3 3 2 4 1 ...

correct output
2064735712

user output
2064735712

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
8 1 2 6 8 6 9 1 4 9 9 8 6 3 3 ...

correct output
378551508

user output
378551508

Test 15

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
5 2 8 9 4 10 1 8 9 9 8 1 7 8 9...

correct output
457149308

user output
457149308

Test 16

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
7 6 2 6 1 3 10 4 6 3 5 2 2 10 ...

correct output
471575451

user output
471575451

Test 17

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
6 2 2 3 8 7 2 10 8 9 6 3 10 5 ...

correct output
620685913

user output
620685913

Test 18

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
4 5 3 8 2 8 5 9 6 3 7 5 1 6 9 ...

correct output
1132427688

user output
1132427688

Test 19

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
15 9 7 18 3 20 19 20 17 16 16 ...

correct output
333300698

user output
333300698

Test 20

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
19 18 17 16 15 14 13 12 11 10 ...

correct output
660514815

user output
660514815

Test 21

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
4999000000000

user output
4999000000000

Test 22

Group: 2, 3

Verdict: ACCEPTED

input
5000
5000 5000 5000 5000 5000 5000 ...

correct output
0

user output
0

Test 23

Group: 2, 3

Verdict: ACCEPTED

input
5000
4999 4998 4997 4996 4995 4994 ...

correct output
576616581

user output
576616581

Test 24

Group: 2, 3

Verdict: ACCEPTED

input
5000
3343 3711 2568 137 2621 3850 4...

correct output
671570

user output
671570

Test 25

Group: 2, 3

Verdict: ACCEPTED

input
5000
119 203 420 133 175 334 461 10...

correct output
85700253

user output
85700253

Test 26

Group: 2, 3

Verdict: ACCEPTED

input
5000
8 6 2 1 4 5 7 3 4 2 1 10 3 6 6...

correct output
193210576015

user output
193210576015

Test 27

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 2 1 2 2 1 2 2 1 1 1 2 1 2 2 ...

correct output
1576581428593

user output
1576581428593

Test 28

Group: 2, 3

Verdict: ACCEPTED

input
5000
300 1937 2136 770 429 2388 197...

correct output
3584707

user output
3584707

Test 29

Group: 2, 3

Verdict: ACCEPTED

input
5000
949 46 29 2237 2413 36 42 1162...

correct output
3210354

user output
3210354

Test 30

Group: 2, 3

Verdict: ACCEPTED

input
5000
1557 1727 1787 360 1698 2423 1...

correct output
3177107

user output
3177107

Test 31

Group: 2, 3

Verdict: ACCEPTED

input
5000
484 1991 2309 1326 1901 2426 8...

correct output
4863018

user output
4863018

Test 32

Group: 2, 3

Verdict: ACCEPTED

input
5000
1833 459 1994 2050 272 31 708 ...

correct output
2876923

user output
2876923

Test 33

Group: 2, 3

Verdict: ACCEPTED

input
4999
530 2248 1916 859 2394 1403 24...

correct output
5194452

user output
5194452

Test 34

Group: 3

Verdict: ACCEPTED

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

correct output
199999000000000

user output
199999000000000

Test 35

Group: 3

Verdict: ACCEPTED

input
200000
200000 200000 200000 200000 20...

correct output
0

user output
0

Test 36

Group: 3

Verdict:

input
200000
199999 199998 199997 199996 19...

correct output
819945000

user output
(empty)

Test 37

Group: 3

Verdict: ACCEPTED

input
200000
9036 179861 197509 187949 9444...

correct output
59563

user output
59563

Test 38

Group: 3

Verdict: ACCEPTED

input
200000
357 1516 141 399 860 1591 544 ...

correct output
247414000

user output
247414000

Test 39

Group: 3

Verdict: ACCEPTED

input
200000
10 4 1 7 1 8 8 4 8 2 2 4 2 4 8...

correct output
7789595210075

user output
7789595210075

Test 40

Group: 3

Verdict: ACCEPTED

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

correct output
62777824801872

user output
62777824801872

Test 41

Group: 3

Verdict: ACCEPTED

input
200000
9473 42975 69773 60909 9354 20...

correct output
76814

user output
76814

Test 42

Group: 3

Verdict: ACCEPTED

input
200000
31087 18493 14158 65333 95850 ...

correct output
180614

user output
180614

Test 43

Group: 3

Verdict: ACCEPTED

input
200000
66563 17340 2293 5101 35636 96...

correct output
56642

user output
56642

Test 44

Group: 3

Verdict: ACCEPTED

input
200000
4005 35201 22254 56956 49098 7...

correct output
287201

user output
287201

Test 45

Group: 3

Verdict: ACCEPTED

input
200000
99266 91407 53419 70750 93505 ...

correct output
54045

user output
54045

Test 46

Group: 3

Verdict: ACCEPTED

input
199999
23098 95019 27998 22880 40713 ...

correct output
184595

user output
184595