— Dark mode

Datatähti 2026 alku

Hypyt

  • Start: 2025-10-27 00:00:00
  • End: 2025-11-10 00:00:00
Submission details
Task:Hypyt
Sender:asonnine
Submission time:2025-10-31 14:22:28 +0200
Language:Rust (2021)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5details
#2--1, 2, 3, 4, 5details
#3--1, 2, 3, 4, 5details
#4--1, 2, 3, 4, 5details
#50.00 s1, 2, 3, 4, 5details
#6--2, 5details
#7--2, 5details
#8--2, 5details
#9--3, 4, 5details
#10--3, 4, 5details
#11--3, 4, 5details
#12--4, 5details
#13--4, 5details
#14--4, 5details
#15--5details
#16--5details
#17--5details
#18--5details
#19--5details
#20--5details
#21--5details
#22ACCEPTED0.00 s1, 2, 3, 4, 5details
#23ACCEPTED0.00 s1, 2, 3, 4, 5details
#24ACCEPTED0.44 s5details
#25ACCEPTED0.33 s5details
#26--5details
#27ACCEPTED0.33 s5details

Code

use std::{io, usize, vec};

#[derive(Debug, Clone)]
struct Row {
    connections: Vec<usize>,
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let (n, m, q): (usize, usize, usize) = {
        let mut iter = input.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };
    let mut map: Vec<Vec<bool>> = Vec::new();
    for _ in 0..n {
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        map.push(input.trim().chars().map(|x| x == '.').collect());
    }
    let mut rows: Vec<Row> = vec![
        Row {
            connections: Vec::new()
        };
        n
    ];
    for row in 0..n {
        for column in 0..m {
            if map[row][column] {
                for rowi in 0..n {
                    if map[rowi][column] {
                        rows[row].connections.push(rowi);
                    }
                }
            }
        }
    }

    let mut queries: Vec<((usize, usize), (usize, usize))> = Vec::new();
    for _ in 0..q {
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let (y1, x1, y2, x2): (usize, usize, usize, usize) = {
            let mut iter = input.split_whitespace();
            (
                iter.next().unwrap().parse().unwrap(),
                iter.next().unwrap().parse().unwrap(),
                iter.next().unwrap().parse().unwrap(),
                iter.next().unwrap().parse().unwrap(),
            )
        };
        queries.push(((x1 - 1, y1 - 1), (x2 - 1, y2 - 1)));
    }

    let rows = rows;
    let queries = queries;

    dbg!(&rows);

    for query in queries {
        println!("{}", process_query(&rows, &map, query));
    }
}

// NOTE: Needs to be O(n+m)
fn process_query(
    map_rows: &Vec<Row>,
    map: &Vec<Vec<bool>>,
    query: ((usize, usize), (usize, usize)),
) -> i32 {
    let mut steps = 1;
    let rows = map_rows.len();
    let mut used_rows = vec![false; rows];

    if query.0 == query.1 {
        return 0;
    } else if query.0.0 == query.1.0 || query.0.1 == query.1.1 {
        return 1;
    }

    let mut process_rows: Vec<usize> = Vec::new();

    process_rows.push(query.0.1);
    for row in 0..rows {
        if map[row][query.0.0] {
            process_rows.push(row);
            used_rows[row] = true;
        }
    }

    steps += 2;

    let mut can_continue = false;

    loop {
        let mut new_process_rows: Vec<usize> = Vec::new();

        for row in &process_rows {
            for rowi in &map_rows[*row].connections {
                if !used_rows[*rowi] {
                    used_rows[*rowi] = true;
                    new_process_rows.push(*rowi);
                    can_continue = true;
                    if *rowi == query.1.1 {
                        if map[*row][query.1.0] {
                            return steps + 1;
                        } else {
                            return steps;
                        }
                    }
                }
            }
        }

        if !can_continue {
            return -1;
        }

        process_rows = new_process_rows;
    }
}

Test details

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
4 6 5
.*.***
*...**
*****.
*..*.*
...
view save

correct output
1
0
3
3
-1
view save

user output
1
0
3
3
-1
view save

Error:
[input/code.rs:62] &rows = [
    Row {
        connections: [
            0,
            0,
            1,
            3,
        ],
    },
    Row {
        connections: [
            1,
            3,
            0,
            1,
            3,
            1,
        ],
    },
    Row {
        connections: [
            2,
        ],
    },
    Row {
        connections: [
            1,
            3,
            0,
            1,
            3,
            3,
        ],
    },
]

Test 2

Group: 1, 2, 3, 4, 5

Verdict:

input
10 10 10
..........
.....*....
........*.
*.*....*..
...
view save

correct output
1
2
1
2
2
...
view save

user output
(empty)

Test 3

Group: 1, 2, 3, 4, 5

Verdict:

input
10 10 10
*...***.**
*****.*...
**..**.**.
..**.**.*.
...
view save

correct output
1
2
2
1
2
...
view save

user output
(empty)

Test 4

Group: 1, 2, 3, 4, 5

Verdict:

input
10 10 10
***.*.****
**********
*.********
.*.***.**.
...
view save

correct output
3
4
2
3
4
...
view save

user output
(empty)

Test 5

Group: 1, 2, 3, 4, 5

Verdict:

input
10 10 1
.****.****
**.**..***
**********
*******..*
...
view save

correct output
7
view save

user output
3
view save

Feedback: Incorrect character on line 1 col 1: expected "7", got "3"
Error:
[input/code.rs:62] &rows = [
    Row {
        connections: [
            0,
            5,
            0,
            1,
            8,
        ],
    },
    Row {
        connections: [
            1,
            0,
            1,
            8,
            1,
            9,
        ],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [
            3,
            5,
            6,
            3,
        ],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [
            0,
            5,
            3,
            5,
            6,
        ],
    },
    Row {
        connections: [
            6,
            3,
            5,
            6,
        ],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [
            0,
            1,
            8,
        ],
    },
    Row {
        connections: [
            9,
            1,
            9,
        ],
    },
]

Test 6

Group: 2, 5

Verdict:

input
250 250 250
.*...*.....*******..**...*.......
view save

correct output
2
3
3
2
2
...
view save

user output
(empty)

Test 7

Group: 2, 5

Verdict:

input
250 250 250
...*......**.**.*.*..**..*..**...
view save

correct output
2
2
2
2
3
...
view save

user output
(empty)

Test 8

Group: 2, 5

Verdict:

input
250 250 250
**..**..****.****.*.***.***..*...
view save

correct output
2
3
3
3
3
...
view save

user output
(empty)

Test 9

Group: 3, 4, 5

Verdict:

input
40 40 200000
...*.**.*..*.............*.*.....
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 10

Group: 3, 4, 5

Verdict:

input
40 40 200000
**.**..*.*.*.******....****.*....
view save

correct output
2
1
3
2
2
...
view save

user output
(empty)

Test 11

Group: 3, 4, 5

Verdict:

input
40 40 200000
.*.*.**.*****.***.*.****.**.**...
view save

correct output
3
3
3
3
3
...
view save

user output
(empty)

Test 12

Group: 4, 5

Verdict:

input
80 80 200000
*....**.***..****...*.....*......
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 13

Group: 4, 5

Verdict:

input
80 80 200000
.***.*..*.***..*****....**...*...
view save

correct output
3
2
2
3
2
...
view save

user output
(empty)

Test 14

Group: 4, 5

Verdict:

input
80 80 200000
*******.*****.*..*..****...***...
view save

correct output
2
3
1
2
2
...
view save

user output
(empty)

Test 15

Group: 5

Verdict:

input
250 250 200000
*....*..*..*..**..*.........**...
view save

correct output
3
2
2
2
2
...
view save

user output
(empty)

Test 16

Group: 5

Verdict:

input
250 250 200000
..*....*..*......*.**.*.*..***...
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 17

Group: 5

Verdict:

input
250 250 200000
*..*.*****.*********.****.****...
view save

correct output
3
3
2
2
2
...
view save

user output
(empty)

Test 18

Group: 5

Verdict:

input
250 250 200000
*********.**********.******.**...
view save

correct output
3
3
3
3
3
...
view save

user output
(empty)

Test 19

Group: 5

Verdict:

input
250 250 200000
.*****************************...
view save

correct output
104
422
145
93
65
...
view save

user output
(empty)

Test 20

Group: 5

Verdict:

input
250 250 200000
..****************************...
view save

correct output
57
155
38
65
98
...
view save

user output
(empty)

Test 21

Group: 5

Verdict:

input
250 250 200000
.*****************************...
view save

correct output
498
498
498
498
498
...
view save

user output
(empty)

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
10 1 10
*
*
.
*
...
view save

correct output
0
1
1
0
0
...
view save

user output
0
1
1
0
0
...
view save

Error:
[input/code.rs:62] &rows = [
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [
            2,
            5,
            9,
        ],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [
            2,
            5,
            9,
        ],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [
            2,
            5,
            9,
        ],
    },
]

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
1 10 10
........*.
1 7 1 10
1 4 1 7
1 5 1 1
...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Error:
[input/code.rs:62] &rows = [
    Row {
        connections: [
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
        ],
    },
]

Test 24

Group: 5

Verdict: ACCEPTED

input
250 1 200000
*
.
*
.
...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Error:
[input/code.rs:62] &rows = [
    Row {
        connections: [],
    },
    Row {
        connections: [
            1,
            3,
            4,
            7,
            9,
            13,
            14,
            17,
            18,
            22,
            25,
            30,
            31,
            32,
            34,
            35,
            36,
            41,
            42,
            43,
            45,
            46,
            47,
            48,
            50,
            52,
            57,
            61,
            64,
            67,
            68,
            69,
            70,
            71,
            72,
            75,
            76,
            77,
            78,
            81,
            83,
            84,
            85,
            86,
            87,
            88,
            91,
            92,
            93,
            94,
            96,
            97,
            98,
            100,
            103,
            106,...

Test 25

Group: 5

Verdict: ACCEPTED

input
1 250 200000
*.*.*...*.*.**.***..**.*.*..**...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Error:
[input/code.rs:62] &rows = [
    Row {
        connections: [
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,...

Test 26

Group: 5

Verdict:

input
250 250 200000
.................................
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 27

Group: 5

Verdict: ACCEPTED

input
250 250 200000
******************************...
view save

correct output
0
0
0
0
0
...
view save

user output
0
0
0
0
0
...
view save

Error:
[input/code.rs:62] &rows = [
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    Row {
        connections: [],
    },
    R...

Tasks

A Palindromi-B Monikulmio-C Tulkki-D Maalaus-E Hypyt-F Lukujono-

Submissions (asonnine)

2025-11-09 13:26:58 1002025-11-09 13:19:43 602025-11-09 13:18:28 602025-11-09 13:16:47 602025-11-09 12:53:03 302025-11-09 11:59:04 02025-11-09 11:10:37 02025-11-07 13:24:46 452025-11-07 09:51:15 02025-11-06 16:39:42 452025-11-06 16:10:31 452025-11-06 16:03:15 302025-11-06 16:01:38 02025-11-06 14:14:51 02025-11-06 13:56:23 02025-11-06 11:51:09 452025-11-05 09:35:07 02025-11-05 09:30:44 02025-11-01 10:30:38 02025-10-31 23:55:59 02025-10-31 23:45:14 02025-10-31 14:24:49 02025-10-31 14:22:28 02025-10-31 14:15:25 02025-10-31 14:12:42 02025-10-31 13:57:14 02025-10-31 13:48:21 02025-10-29 10:36:24 302025-10-28 12:10:07 452025-10-28 08:52:52 302025-10-28 08:31:28 302025-10-27 18:15:18 02025-10-27 18:02:22 0