Submission #1123948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123948		LucaIlie	Maze (JOI23_ho_t3)	C++20	51 / 100	2110 ms	586432 KiB

Main

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using namespace std;

struct cell {
    int dir, l, c;
};

struct distancee {
    int dist, dir, distL, distC;
};

bool operator < ( distancee a, distancee b ) {
    if ( a.dist == b.dist ) {
        int valA = (a.dir < 2 ? max( a.distL, a.distC ) : min( a.distL, a.distC ));
        int valB = (b.dir < 2 ? max( b.distL, b.distC ) : min( b.distL, b.distC ));
        return valA < valB;
    }
    return a.dist < b.dist;
}

struct elempq {
    cell c;
    distancee d;

    bool operator < ( const elempq &x ) const {
        return x.d < d;
    }
};

const int MAX_N = 2500;
const int INF = 1e7;
int dl[4] = { 1, 0, -1, 0 }, dc[4] = { 0, 1, 0, -1 };
vector<distancee> minDist[5][MAX_N];
vector<bool> isBlocked[MAX_N], vis[5][MAX_N];
priority_queue<elempq> pq[MAX_N * MAX_N];

int main() {
    int n, m, k, sl, sc, gl, gc;

    scanf( "%d%d%d", &n, &m, &k );
    scanf( "%d%d", &sl, &sc );
    scanf( "%d%d", &gl, &gc );
    for ( int l = 0; l <= n + 1; l++ ) {
        isBlocked[l].resize( m + 2 );
        for ( int d = 0; d < 5; d++ ) {
            minDist[d][l].resize( m + 2 );
            for ( int c = 0; c <= m + 1; c++ )
                minDist[d][l][c] = { INF, d, 0, 0 };
            vis[d][l].resize( m + 2 );
        }
    }
    for ( int l = 1; l <= n; l++ ) {
        char ch;
        scanf( "%c", &ch );
        for ( int c = 1; c <= m; c++ ) {
            scanf( "%c", &ch );
            isBlocked[l][c] = (ch == '#');
        }
    }
    for ( int l = 0; l <= n + 1; l++ ) {
        isBlocked[l][0] = isBlocked[l][m + 1] = true;
        for ( int d = 0; d < 5; d++ )
            minDist[d][l][0] = minDist[d][l][m + 1] = { -INF, d, 0, 0 };
    }
    for ( int c = 0; c <= m + 1; c++ ) {
        isBlocked[0][c] = isBlocked[n + 1][c] = true;
        for ( int d = 0; d < 5; d++ )
            minDist[d][0][c] = minDist[d][n + 1][c] = { -INF, d, 0, 0 };
    }

    minDist[4][sl][sc] = { 0, 4, 0, 0 };
    pq[0].push( { 4, sl, sc, minDist[4][sl][sc] } );
    for ( int dst = 0; dst <= n * m && dst <= minDist[4][gl][gc].dist; dst++) {
        while ( !pq[dst].empty()) {
            cell a = pq[dst].top().c;
            distancee dd = pq[dst].top().d;
            pq[dst].pop();

            int dir = a.dir, l = a.l, c = a.c;
            //printf( "celula %d %d %d cu distanta %d %d %d %d\n", dir, l, c, minDist[dir][l][c].dir, minDist[dir][l][c].dist, minDist[dir][l][c].distL, minDist[dir][l][c].distC );

            if ( minDist[dir][l][c] < dd )
                continue;

            if ( dir == 4 ) {
                for ( int d = 0; d < 4; d++ ) {
                    int newL = l + dl[d], newC = c + dc[d];
                    distancee newDist = minDist[dir][l][c];
                    if ( isBlocked[newL][newC] ) {
                        newDist.dir = 0;
                        newDist.distL = newDist.distC = 1;
                    }
                    if ( newDist < minDist[newDist.dir][newL][newC] ) {
                        minDist[newDist.dir][newL][newC] = newDist;
                        pq[newDist.dist].push( { newDist.dir, newL, newC, minDist[newDist.dir][newL][newC] } );
                    }
                }
            } else {
                for ( int d = 0; d < 4; d++ ) {
                    int newL = l + dl[d], newC = c + dc[d];
                    distancee newDist = minDist[dir][l][c];
                    if ( !isBlocked[newL][newC] ) {
                        newDist.dir = 4;
                        newDist.dist++;
                        newDist.distL = newDist.distC = 0;
                        if ( newDist < minDist[newDist.dir][newL][newC] ) {
                            minDist[newDist.dir][newL][newC] = newDist;
                            pq[newDist.dist].push( { newDist.dir, newL, newC, minDist[newDist.dir][newL][newC] } );
                        }
                    }
                    newDist = minDist[dir][l][c];
                    if ( newDist.distL == k ) {
                        if ( newDist.distC == k ) {
                            newDist.dist++;
                            newDist.dir = 0;
                            newDist.distL = newDist.distC = 1;
                        } else {
                            if ( d % 2 == 0 )
                                continue;
                            if ( newDist.distC == 1 )
                                newDist.dir += 2;
                            newDist.distC++;
                        }
                    } else if ( newDist.distC == k ) {
                        if ( d % 2 == 1 )
                            continue;
                        if ( newDist.distL == 1 )
                            newDist.dir += 2;
                        newDist.distL++;
                    } else if ( newDist.distL == 1 ) {
                        if ( newDist.distC == 1 ) {
                            if ( d % 2 == 0 ) {
                                newDist.distL++;
                                newDist.dir = 0;
                            } else {
                                newDist.distC++;
                                newDist.dir = 1;
                            }
                        } else {
                            if ( d % 2 == 0 )
                                continue;
                            newDist.distC++;
                        }
                    } else if ( newDist.distC == 1 ) {
                        if ( d % 2 == 1 )
                            continue;
                        newDist.distL++;
                    }
                    if ( newDist < minDist[newDist.dir][newL][newC] ) {
                        minDist[newDist.dir][newL][newC] = newDist;
                        pq[newDist.dist].push( { newDist.dir, newL, newC, minDist[newDist.dir][newL][newC] } );
                    }
                }
            }
        }
    }

    int ans = minDist[4][gl][gc].dist;
    for ( int l = 1; l <= n; l++ ) {
        for ( int c = 1; c <= m; c++ ) {
            if ( !isBlocked[l][c] && abs( l - gl ) <= k - 1 && abs( c - gc ) <= k - 1 )
                ans = min( ans, minDist[4][l][c].dist + 1 );
        }
    }

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf( "%d%d%d", &n, &m, &k );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf( "%d%d", &sl, &sc );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf( "%d%d", &gl, &gc );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf( "%c", &ch );
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |             scanf( "%c", &ch );
      |             ~~~~~^~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6