Submission #1123943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123943		LucaIlie	Maze (JOI23_ho_t3)	C++20	86 / 100	2102 ms	356952 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;
    }
};

class MaxHeap {
    elempq* arr;

    int maxSize;
    int heapSize;

public:
    MaxHeap(int maxSize);

    void MaxHeapify(int);

    int parent(int i)
    {
        return (i - 1) / 2;
    }

    int lChild(int i)
    {
        return (2 * i + 1);
    }

    int rChild(int i)
    {
        return (2 * i + 2);
    }

    elempq removeMax();

    elempq getMax()
    {
        return arr[0];
    }

    int curSize()
    {
        return heapSize;
    }

    void insertKey(elempq x);
};

MaxHeap::MaxHeap(int totSize)
{
    heapSize = 0;
    maxSize = totSize;
    arr = new elempq[totSize];
}

void MaxHeap::insertKey(elempq x)
{
    if (heapSize == maxSize) {
        cout << "\nOverflow: Could not insertKey\n";
        return;
    }
    heapSize++;
    int i = heapSize - 1;
    arr[i] = x;
    while (i != 0 && arr[parent(i)] < arr[i]) {
        swap(arr[i], arr[parent(i)]);
        i = parent(i);
    }
}

elempq MaxHeap::removeMax()
{
    if (heapSize == 1) {
        heapSize--;
        return arr[0];
    }

    elempq root = arr[0];
    arr[0] = arr[heapSize - 1];
    heapSize--;

    // To restore the property
    // of the Max heap.
    MaxHeapify(0);

    return root;
}

void MaxHeap::MaxHeapify(int i)
{
    int l = lChild(i);
    int r = rChild(i);
    int largest = i;
    if (l < heapSize && arr[i] < arr[l])
        largest = l;
    if (r < heapSize && arr[largest] < arr[r])
        largest = r;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        MaxHeapify(largest);
    }
}

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];
MaxHeap pq( INF );

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.insertKey( { 4, sl, sc, minDist[4][sl][sc] } );
    while ( pq.curSize() > 0 ) {
        cell a = pq.getMax().c;
        distancee dd = pq.getMax().d;
        pq.removeMax();

        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.insertKey( { 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.insertKey( { 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.insertKey( { 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:140:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |     scanf( "%d%d%d", &n, &m, &k );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:141:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |     scanf( "%d%d", &sl, &sc );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |     scanf( "%d%d", &gl, &gc );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         scanf( "%c", &ch );
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:156:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |             scanf( "%c", &ch );
      |             ~~~~~^~~~~~~~~~~~~

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