— 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:OorigamiK
Submission time:2025-11-01 02:41:51 +0200
Language:C++ (C++20)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5details
#20.00 s1, 2, 3, 4, 5details
#30.00 s1, 2, 3, 4, 5details
#40.00 s1, 2, 3, 4, 5details
#5ACCEPTED0.00 s1, 2, 3, 4, 5details
#60.05 s2, 5details
#70.04 s2, 5details
#80.03 s2, 5details
#90.16 s3, 4, 5details
#100.16 s3, 4, 5details
#110.16 s3, 4, 5details
#120.16 s4, 5details
#130.16 s4, 5details
#140.16 s4, 5details
#150.22 s5details
#160.21 s5details
#170.21 s5details
#180.22 s5details
#190.22 s5details
#200.21 s5details
#21ACCEPTED0.33 s5details
#22ACCEPTED0.00 s1, 2, 3, 4, 5details
#23ACCEPTED0.00 s1, 2, 3, 4, 5details
#24ACCEPTED0.20 s5details
#25ACCEPTED0.19 s5details
#260.24 s5details
#27ACCEPTED0.21 s5details

Code

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
#include <bitset>

using namespace std;

struct Info{
    int dist;
    int lastStep;
};

int minDist(bitset<250> grid[250], bitset<250> rowAccess[250], Info rowDists [250][250], int n, int x1, int y1, int x2, int y2){
    if (!grid[y2][x2] || rowDists[y1][y2].dist==-1){
        return -1;
    }
    if (x1==x2 && y1==y2){
        return 0;
    }
    if (x1==x2 || y1==y2){
        return 1;
    }

    bitset<250> parities;

    int k = rowDists[y1][y2].dist;
    int startParity=0;
    for (int y=0;y<n;y++){
        if (grid[y][x1] && rowDists[y][y2].dist==k-1){
            startParity=1;
            parities.set(rowDists[y][y2].lastStep);
            
        }
    }

    if (startParity==1){
        for (int y=0;y<n;y++){
            if (grid[y][x2] && parities[y]){
                return 2*k-1;
            }
        }
        return 2*k;

    }
    for (int y=0;y<n;y++){
        if (grid[y][x2]){
            if (rowDists[y][y1].dist==k-1){
                return 2*k;
            }
        }
    }
    return 2 * k + 1;
}

void calcRowDists(bitset<250> rowAccess[250], Info rowDists[250][250], const int n){
    for (int i=0;i<n;i++){
        bitset<250> curRows;
        bitset<250> nextRows;
        nextRows.set(i);
        bitset<250> doneRows;
        doneRows.set(i);
        rowDists[i][i].dist=0;
        int k=1;
        int j=1;
        while (j!=0){
            j=0;
            swap(curRows, nextRows);
            nextRows.reset();
            for (int l=0;l<n;l++){
                if (curRows[l]){
                    int curRow=l;
                    for (int row=0;row<n;row++){
                        if (rowAccess[curRow][row] && !doneRows[row]){
                            nextRows.set(row);
                            doneRows.set(row);
                            rowDists[i][row]={k, curRow};
                            j++;
                        }
                    }
                }
            }
            k++;
        }
    }
}

int main(){
    int n,m,q;
    cin>>n>>m>>q;

    bitset<250> grid[250];
    bitset<250> rowAccess[250];
    Info rowDists[250][250];
    for (int i=0;i<250;i++){
        for (int j=0;j<250;j++){
            rowDists[i][j]={-1,-1};
        }
    }

    for (int i=0;i<n;i++){
        string s;
        cin>>s;
        for (int j=0;j<m;j++){
            grid[i][j]=(s[j]=='.');
        }
    }

    for (int i=0;i<m;i++){
        vector<int> rows;
        for (int j=0;j<n;j++){
            if (grid[j][i]){
                rows.push_back(j);
            }
        }
        for (int row : rows){
            for (int row1 : rows){
                rowAccess[row][row1]=true;
            }
        }
    }

    calcRowDists(rowAccess, rowDists, n);    

    vector<int> input(4*q, 0);
    for (int i=0;i<q;i++){
        int x1,x2,y1,y2;
        cin>>y1>>x1>>y2>>x2;
        input[4*i+0]=x1;
        input[4*i+1]=y1;
        input[4*i+2]=x2;
        input[4*i+3]=y2;
    }
    
    for (int i=0;i<q;i++){
        int x1=input[4*i+0];
        int y1=input[4*i+1];
        int x2=input[4*i+2];
        int y2=input[4*i+3];
        cout<<minDist(grid, rowAccess, rowDists , n, x1-1, y1-1, x2-1, y2-1)<<"\n";
    }
    return 0;
}

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

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)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

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)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

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)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

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

correct output
7
view save

user output
7
view save

Test 6

Group: 2, 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 7

Group: 2, 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 8

Group: 2, 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

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)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

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)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

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)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 12

Group: 4, 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 13

Group: 4, 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 14

Group: 4, 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 15

Group: 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 16

Group: 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 17

Group: 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 18

Group: 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 19

Group: 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 20

Group: 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

Test 21

Group: 5

Verdict: ACCEPTED

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

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

user output
498
498
498
498
498
...
view save

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

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

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

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

Test 26

Group: 5

Verdict:

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

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

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 18446744073709551615) >= _Nb (which is 250)

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

Tasks

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

Submissions (OorigamiK)

2025-11-01 02:43:14 1002025-11-01 02:42:41 02025-11-01 02:41:51 02025-11-01 02:28:25 02025-11-01 02:26:49 602025-11-01 02:25:06 602025-11-01 02:23:17 02025-11-01 02:22:42 02025-11-01 02:14:44 602025-11-01 02:12:29 602025-11-01 02:11:24 602025-11-01 02:10:17 602025-11-01 02:01:50 602025-11-01 01:53:41 02025-11-01 01:45:37 602025-11-01 01:41:25 602025-11-01 01:40:12 602025-11-01 01:39:39 2025-11-01 01:37:55 602025-11-01 01:37:34 602025-11-01 01:37:14 02025-11-01 01:36:02 02025-11-01 01:28:44 02025-11-01 01:27:24 02025-11-01 01:00:01 602025-11-01 00:58:00 602025-11-01 00:34:02 02025-10-31 23:28:26 452025-10-31 23:18:48 02025-10-31 23:12:56 02025-10-31 22:57:40 302025-10-31 20:48:26 302025-10-31 20:45:12 02025-10-31 20:43:26 02025-10-31 20:28:47 02025-10-31 20:19:10 02025-10-31 20:08:26 02025-10-31 20:06:19 02025-10-29 11:14:18 102025-10-29 09:25:44 102025-10-29 09:19:21 102025-10-28 20:56:57 10