— 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:xiaou0
Submission time:2025-10-27 17:03:35 +0200
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.10 s1, 2, 3, 4, 5details
#20.10 s1, 2, 3, 4, 5details
#30.10 s1, 2, 3, 4, 5details
#40.10 s1, 2, 3, 4, 5details
#5ACCEPTED0.10 s1, 2, 3, 4, 5details
#60.27 s2, 5details
#70.27 s2, 5details
#80.20 s2, 5details
#90.55 s3, 4, 5details
#100.55 s3, 4, 5details
#110.54 s3, 4, 5details
#120.56 s4, 5details
#130.56 s4, 5details
#140.55 s4, 5details
#150.74 s5details
#160.74 s5details
#170.68 s5details
#180.64 s5details
#190.64 s5details
#200.64 s5details
#21ACCEPTED0.62 s5details
#22ACCEPTED0.10 s1, 2, 3, 4, 5details
#23ACCEPTED0.10 s1, 2, 3, 4, 5details
#24ACCEPTED0.58 s5details
#25ACCEPTED0.57 s5details
#260.68 s5details
#27ACCEPTED0.64 s5details

Code

#include <bits/stdc++.h>
using namespace std;

const int N=255;
int n,m,q;
bool grid[N][N];// *=0, .=1
/*
Only consider the connection between all rows and columns
For code convenience, using the adjacency matrix :/ (Not that slow)
*/
bool adjrow[N][N],adjcol[N][N];
int dprow[N][N][N],dpcol[N][N][N];
int oddity[N][N];
 
void debug(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            cout<<adjrow[i][j];
        cout<<endl;
    }
    cout<<"---"<<endl;
    for(int i=1;i<=m;++i){
        for(int j=1;j<=m;++j)
            cout<<adjcol[i][j];
        cout<<endl;
    }
    cout<<"---"<<endl;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            cout<<(dprow[n][i][j]>=0x1f1f1f?-1:dprow[n][i][j])<<" ";
        cout<<endl;
    }
    cout<<"---"<<endl;
    for(int i=1;i<=m;++i){
        for(int j=1;j<=m;++j)
            cout<<(dpcol[m][i][j]>=0x1f1f1f?-1:dpcol[m][i][j])<<" ";
        cout<<endl;
    }
    cout<<"---"<<endl;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            cout<<oddity[i][j]<<" ";
        cout<<endl;
    }
}
 
void floyd(){
    memset(dprow,0x1f1f1f,sizeof(dprow));
    memset(dpcol,0x1f1f1f,sizeof(dpcol));
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            if(i==j)dprow[0][i][j]=0;
            else if(adjrow[i][j]) dprow[0][i][j]=1;
        }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                dprow[k][i][j]=min(dprow[k-1][i][j],dprow[k-1][i][k]+dprow[k-1][k][j]);
            }
        }
    }
    for(int i=1;i<=m;++i)
        for(int j=1;j<=m;++j){
            if(i==j)dpcol[0][i][j]=0;
            else if(adjcol[i][j]) dpcol[0][i][j]=1;
        }
    for(int k=1;k<=m;k++){
        for(int i=1;i<=m;++i){
            for(int j=1;j<=m;++j){
                dpcol[k][i][j]=min(dpcol[k-1][i][j],dpcol[k-1][i][k]+dpcol[k-1][k][j]);
            }
        }
    }
}

struct Node{
    int x,y;
};

void bfs(int x,int y){
    queue<Node>Q;
    Q.push(Node{x,y});
    oddity[x][y]=2;
    while(!Q.empty()){
        Node now=Q.front();
        Q.pop();
        int nx=now.x;
        int ny=now.y;
        for(int i=1;i<=n;++i){
            if(oddity[i][ny]!=0)continue;
            if(!grid[i][ny])continue;
            oddity[i][ny]=(oddity[nx][ny]==2?1:2);
            Q.push(Node{i,ny});
        }
        for(int i=1;i<=m;++i){
            if(oddity[nx][i]!=0)continue;
            if(!grid[nx][i])continue;
            oddity[nx][i]=(oddity[nx][i]==2?1:2);
            Q.push(Node{nx,i});
        }
    }
}
 
int main(){
    cin>>n>>m>>q;
    char tmpchar;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            {cin>>tmpchar;
            grid[i][j]=(tmpchar=='.'?1:0);}
    for(int i=1;i<=n;++i)//Init the adjacency matrix O(n^3)
        for(int j=1;j<i;++j){
            for(int k=1;k<=m;++k)
                adjrow[i][j]|=(grid[i][k]&&grid[j][k]);
            adjrow[j][i]=adjrow[i][j];
        }
    for(int i=1;i<=m;++i)//Init the adjacency matrix O(n^3)
        for(int j=1;j<i;++j){
            for(int k=1;k<=n;++k)
                adjcol[i][j]|=(grid[k][i]&&grid[k][j]);
            adjcol[j][i]=adjcol[i][j];
        }
    floyd();//Floyd algo. O(n^3)
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(oddity[i][j]==0&&grid[i][j])bfs(i,j);
    // debug();
    for(int i=1;i<=q;++i){//Queries
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x1==x2&&y1==y2){
            cout<<0<<endl;
            continue;
        }
        else if(x1==x2||y1==y2){
            cout<<1<<endl;
            continue;
        }
        int drow=dprow[n][x1][x2];
        int dcol=dpcol[m][y1][y2];
        if(drow>1000000||dcol>1000000)cout<<-1<<endl;
        else if(drow!=dcol)cout<<2*min(drow,dcol)+1<<endl;//Some maths can prove that its right
        else if(oddity[x1][y1]==oddity[x2][y2])cout<<2*min(drow,dcol)<<endl;
        else cout<<2*min(drow,dcol)+1<<endl;
    }
    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
1
3
1
3
2
...
view save

Feedback: Incorrect character on line 2 col 1: expected "2", got "3"

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
1
2
3
1
2
...
view save

Feedback: Incorrect character on line 3 col 1: expected "2", got "3"

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
3
5
3
3
4
...
view save

Feedback: Incorrect character on line 2 col 1: expected "4", got "5"

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
2
3
2
2
2
...
view save

Feedback: Incorrect character on line 3 col 1: expected "3", got "2"

Test 7

Group: 2, 5

Verdict:

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

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

user output
2
3
2
2
3
...
view save

Feedback: Incorrect character on line 2 col 1: expected "2", got "3"

Test 8

Group: 2, 5

Verdict:

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

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

user output
2
2
2
3
2
...
view save

Feedback: Incorrect character on line 2 col 1: expected "3", got "2"

Test 9

Group: 3, 4, 5

Verdict:

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

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

user output
3
3
2
2
2
...
view save

Feedback: Incorrect character on line 1 col 1: expected "2", got "3"

Test 10

Group: 3, 4, 5

Verdict:

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

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

user output
3
1
3
2
3
...
view save

Feedback: Incorrect character on line 1 col 1: expected "2", got "3"

Test 11

Group: 3, 4, 5

Verdict:

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

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

user output
3
2
3
3
3
...
view save

Feedback: Incorrect character on line 2 col 1: expected "3", got "2"

Test 12

Group: 4, 5

Verdict:

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

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

user output
2
2
2
3
2
...
view save

Feedback: Incorrect character on line 4 col 1: expected "2", got "3"

Test 13

Group: 4, 5

Verdict:

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

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

user output
3
2
3
2
2
...
view save

Feedback: Incorrect character on line 3 col 1: expected "2", got "3"

Test 14

Group: 4, 5

Verdict:

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

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

user output
3
2
1
3
3
...
view save

Feedback: Incorrect character on line 1 col 1: expected "2", got "3"

Test 15

Group: 5

Verdict:

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

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

user output
3
2
3
3
2
...
view save

Feedback: Incorrect character on line 3 col 1: expected "2", got "3"

Test 16

Group: 5

Verdict:

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

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

user output
2
3
3
3
3
...
view save

Feedback: Incorrect character on line 2 col 1: expected "2", got "3"

Test 17

Group: 5

Verdict:

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

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

user output
3
2
2
2
3
...
view save

Feedback: Incorrect character on line 2 col 1: expected "3", got "2"

Test 18

Group: 5

Verdict:

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

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

user output
2
3
2
2
3
...
view save

Feedback: Incorrect character on line 1 col 1: expected "3", got "2"

Test 19

Group: 5

Verdict:

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

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

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

Feedback: Incorrect character on line 692 col 3: expected "106", got "107"

Test 20

Group: 5

Verdict:

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

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

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

Feedback: Incorrect character on line 76 col 1: expected "2", got "3"

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
2
2
2
2
2
...
view save

Feedback: Incorrect character on line 155 col 1: expected "2", got "3"

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 (xiaou0)

2025-10-28 23:40:55 1002025-10-28 23:40:35 02025-10-28 23:40:23 02025-10-28 23:13:10 302025-10-28 23:11:01 602025-10-28 21:20:52 02025-10-28 20:26:44 02025-10-28 20:14:07 02025-10-28 20:03:55 02025-10-28 13:43:20 302025-10-27 17:05:18 02025-10-27 17:03:35 02025-10-27 15:19:54 02025-10-27 15:18:02 02025-10-27 15:16:35 02025-10-27 15:04:25 02025-10-27 15:02:26 02025-10-27 14:21:23 02025-10-27 13:59:49 02025-10-27 13:01:48 252025-10-27 12:49:19 252025-10-27 10:33:09 30