— 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-28 23:40:35 +0200
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.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
#50.00 s1, 2, 3, 4, 5details
#60.00 s2, 5details
#70.00 s2, 5details
#80.00 s2, 5details
#90.00 s3, 4, 5details
#100.00 s3, 4, 5details
#110.00 s3, 4, 5details
#120.00 s4, 5details
#130.00 s4, 5details
#140.00 s4, 5details
#150.00 s5details
#160.00 s5details
#170.00 s5details
#180.00 s5details
#190.00 s5details
#200.00 s5details
#210.00 s5details
#220.00 s1, 2, 3, 4, 5details
#230.00 s1, 2, 3, 4, 5details
#240.00 s5details
#250.00 s5details
#260.00 s5details
#270.00 s5details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:125:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     freopen("example.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     freopen("exampleout.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
input/code.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);...

Code

/*ver 2.0 : virtual row nodes*/
#include <bits/stdc++.h>
using namespace std;

const int N=255;
int n,m,q;

bool grid[N][N];
bool adjrow[N][N];
bool adjcol[N][N];

struct state{
    int d,first,last;
};

state dprow[N][N][N];
state dpcol[N][N][N];

const int INF=0x3f3f3f;

void floyd(){
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            dprow[0][i][j].last=i;
            dprow[0][i][j].first=j;
            if(i==j)dprow[0][i][j].d=0;
            else if(adjrow[i][j]) dprow[0][i][j].d=2;
            else dprow[0][i][j].d=INF;
        }
    for(int i=1;i<=m;++i)
        for(int j=1;j<=m;++j){
            dpcol[0][i][j].last=i;
            dpcol[0][i][j].first=j;
            if(i==j)dpcol[0][i][j].d=0;
            else if(adjcol[i][j]) dpcol[0][i][j].d=2;
            else dpcol[0][i][j].d=INF;
        }
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                state bef=dprow[k-1][i][j];
                state l=dprow[k-1][i][k];
                state r=dprow[k-1][k][j];
                if(bef.d<=l.d+r.d){
                    dprow[k][i][j]=bef;
                }else{
                    dprow[k][i][j].last=r.last;
                    dprow[k][i][j].first=l.first;
                    dprow[k][i][j].d=l.d+r.d;
                }
            }
        }
    }
    for(int k=1;k<=m;++k){
        for(int i=1;i<=m;++i){
            for(int j=1;j<=m;++j){
                state bef=dpcol[k-1][i][j];
                state l=dpcol[k-1][i][k];
                state r=dpcol[k-1][k][j];
                if(bef.d<=l.d+r.d){
                    dpcol[k][i][j]=bef;
                }else{
                    dpcol[k][i][j].last=r.last;
                    dpcol[k][i][j].first=l.first;
                    dpcol[k][i][j].d=l.d+r.d;
                }
            }
        }
    }
}

void debug(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            cout<<(dprow[n][i][j].d>=0x1f1f1f?-1:dprow[n][i][j].d)<<" ";
        cout<<endl;
    }
    cout<<"---"<<endl;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            cout<<dprow[n][i][j].first<<" ";
        cout<<endl;
    }
    cout<<"---"<<endl;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            cout<<dprow[n][i][j].last<<" ";
        cout<<endl;
    }
}

inline int searchrow(int x1,int y1,int x2,int y2){
    state route=dprow[n][x1][x2];
    int res=route.d;
    int first=route.first;
    int last=route.last;
    if(grid[first][y1]&&grid[x1][y1])--res;
    if(!(grid[last][y2]&&grid[x2][y2]))++res;
    return res;
}
inline int searchcol(int x1,int y1,int x2,int y2){
    state route=dpcol[m][y1][y2];
    int res=route.d;
    int first=route.first;
    int last=route.last;
    if(grid[x1][y1]&&grid[x1][first])--res;
    if(!(grid[x2][last]&&grid[x2][y2]))++res;
    return res;
}
int query(int x1,int y1,int x2,int y2){
    int res=searchrow(x1,y1,x2,y2);
    for(int i=1;i<=n;++i){
        if(i==x2||!grid[i][y2])continue;
        res=min(res,searchrow(x1,y2,i,y2)+1);
    }
    res=min(res,searchcol(x1,y1,x2,y2));
    for(int i=1;i<=m;++i){
        if(i==y2||!grid[x2][i])continue;
        res=min(res,searchcol(x1,y1,x2,i)+1);
    }
    return res;
}

int main(){
    freopen("example.txt","r",stdin);
    freopen("exampleout.txt","w",stdout);
    scanf("%d%d%d",&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)if(grid[i][k]&&grid[j][k]){
                adjrow[i][j]=true;
                adjrow[j][i]=true;
            }
        }
    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)if(grid[k][i]&&grid[k][j]){
                adjcol[i][j]=true;
                adjcol[j][i]=true;
            }
        }
    floyd();
    // debug();
    //Basic Node +1 jump = Row Node (forall).
    for(int i=1;i<=q;++i){//Queries
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(x1==x2&&y1==y2){
            printf("0\n");
            continue;
        }else if(x1==x2||y1==y2){
            printf("1\n");
            continue;
        }else if(grid[x1][y2]||grid[x2][y1]){
            printf("2\n");
            continue;
        }else{
            int res=query(x1,y1,x2,y2);
            printf("%d\n",res>=INF?-1:res);
        }
    }
    return 0;
}
// 2*10^5*500

Test details

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict:

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

correct output
1
0
3
3
-1
view save

user output
(empty)

Feedback: Output is shorter than expected

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)

Feedback: Output is shorter than expected

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)

Feedback: Output is shorter than expected

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)

Feedback: Output is shorter than expected

Test 5

Group: 1, 2, 3, 4, 5

Verdict:

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

correct output
7
view save

user output
(empty)

Feedback: Output is shorter than expected

Test 6

Group: 2, 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 7

Group: 2, 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 8

Group: 2, 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

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)

Feedback: Output is shorter than expected

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)

Feedback: Output is shorter than expected

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)

Feedback: Output is shorter than expected

Test 12

Group: 4, 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 13

Group: 4, 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 14

Group: 4, 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 15

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 16

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 17

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 18

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 19

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 20

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 21

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 22

Group: 1, 2, 3, 4, 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 23

Group: 1, 2, 3, 4, 5

Verdict:

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

Feedback: Output is shorter than expected

Test 24

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 25

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 26

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

Test 27

Group: 5

Verdict:

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

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

user output
(empty)

Feedback: Output is shorter than expected

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