Submission #674450

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
674450	2022-12-24T10:00:20 Z	flashhh	Portals (BOI14_portals)	C++17	100 / 100	293 ms	26384 KB

portals

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define eb emplace

using namespace std;

struct spInfo{
    int distance, row, column;

    spInfo() {}
    spInfo(int _distance, int _row, int _column) {
        distance = _distance; row = _row; column = _column;
    }
};
        
bool operator <(const spInfo &x, const spInfo &y) {
    return (x.distance > y.distance);
}

int xCoordinate[4] = {-1,0,0,1};
int yCoordinate[4] = {0,-1,1,0};

int numRow,numColumn;
pair<int,int> cakeCoordinate,mainCoordinate;
vector<vector<char> > labyrinth;
vector<vector<int> > distances;

void fastIO() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

void Read() {
    cin >> numRow >> numColumn;

    labyrinth.resize(numRow);
    for (int row = 0; row < numRow; ++row) labyrinth[row].resize(numColumn);

    for (int row = 0; row < numRow; ++row)
        for (int column = 0; column < numColumn; ++column) {
            cin >> labyrinth[row][column];

            if (labyrinth[row][column] == 'S') mainCoordinate = {row, column};
            if (labyrinth[row][column] == 'C') cakeCoordinate = {row, column};
        }    
}

void calculate() {
    vector<vector<int> > nearestSide;

    auto buildNearestSide = [&] () -> void {
        nearestSide.resize(numRow);
        for (int row = 0; row < numRow; ++row) nearestSide[row].resize(numColumn);

        for (int row = 0; row < numRow; ++row)
            for (int column = 0; column < numColumn; ++column) {
                if (labyrinth[row][column] == '#') {
                    nearestSide[row][column] = -1;
                    continue;
                }

                nearestSide[row][column] = (int)1e9;

                for (int direction = 0; direction < 4; ++direction) {
                    int adjRow = row + xCoordinate[direction]; int adjColumn = column + yCoordinate[direction];
                    if (adjRow < 0 || adjRow >= numRow || adjColumn < 0 || adjColumn >= numColumn || labyrinth[adjRow][adjColumn] == '#') {
                        nearestSide[row][column] = 0;
                        break;
                    }
                }
            }
        
        queue<pair<int,int> > myQueue;
        for (int row = 0; row < numRow; ++row)
            for (int column = 0; column < numColumn; ++column)
                if (nearestSide[row][column] == 0) myQueue.emplace(row, column);
        
        while (!myQueue.empty()) {
            auto [row, column] = myQueue.front(); myQueue.pop();
            
            for (int direction = 0; direction < 4; ++direction) {
                int adjRow = row + xCoordinate[direction]; int adjColumn = column + yCoordinate[direction];
                if (adjRow < 0 || adjRow >= numRow || adjColumn < 0 || adjColumn >= numColumn) continue;

                if (nearestSide[adjRow][adjColumn] > nearestSide[row][column] + 1) {
                    nearestSide[adjRow][adjColumn] = nearestSide[row][column] + 1;
                    myQueue.emplace(adjRow, adjColumn);
                }
            }
        }
    };

    vector<vector<int> > leftMostWall, rightMostWall, topMostWall, bottomMostWall;

    auto buildNearestWall = [&] () -> void {
        leftMostWall.resize(numRow); rightMostWall.resize(numRow);
        for (int row = 0; row < numRow; ++row) {
            leftMostWall[row].resize(numColumn);
            rightMostWall[row].resize(numColumn);
        }

        for (int row = 0; row < numRow; ++row) {
            int lastColumn = -1;
            for (int column = 0; column < numColumn; ++column) 
                if (labyrinth[row][column] == '#') lastColumn = column;
            else leftMostWall[row][column] = column - lastColumn;
            
            lastColumn = numColumn;
            for (int column = numColumn - 1; column >= 0; --column)
                if (labyrinth[row][column] == '#') lastColumn = column;
            else rightMostWall[row][column] = lastColumn - column;
        }

        topMostWall.resize(numRow); bottomMostWall.resize(numRow);
        for (int row = 0; row < numRow; ++row) {
            topMostWall[row].resize(numColumn);
            bottomMostWall[row].resize(numColumn);
        }

        for (int column = 0; column < numColumn; ++column) {
            int lastRow = -1;
            for (int row = 0; row < numRow; ++row)
                if (labyrinth[row][column] == '#') lastRow = row;
            else topMostWall[row][column] = row - lastRow;

            lastRow = numRow;
            for (int row = numRow - 1; row >= 0; --row)
                if (labyrinth[row][column] == '#') lastRow = row;
            else bottomMostWall[row][column] = lastRow - row;
        }
    };

    buildNearestSide();
    buildNearestWall();

    auto buildDistance = [&] () -> void {
        priority_queue<spInfo> prioQueue;

        distances.resize(numRow);
        for (int row = 0; row < numRow; ++row) distances[row].resize(numColumn, (int)1e9);

        distances[mainCoordinate.first][mainCoordinate.second] = 0;
        prioQueue.emplace(0, mainCoordinate.first, mainCoordinate.second);

        auto updatePrioQueue = [&] (int row, int column, int val) -> void{
            if (distances[row][column] > val) {
                distances[row][column] = val;
                prioQueue.emplace(distances[row][column], row, column);
            }
        };

        while (!prioQueue.empty()) {
            auto [distance, row, column] = prioQueue.top(); prioQueue.pop();
            if (distances[row][column] != distance) continue;

            for (int direction = 0; direction < 4; ++direction) {
                int adjRow = row + xCoordinate[direction]; int adjColumn = column + yCoordinate[direction];
                if (adjRow < 0 || adjRow >= numRow || adjColumn < 0 || adjColumn >= numColumn || labyrinth[adjRow][adjColumn] == '#') continue;

                updatePrioQueue(adjRow, adjColumn, distance + 1);
            }

            int xTeleport, yTeleport;

            xTeleport = row; yTeleport = column - leftMostWall[row][column] + 1;
            updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);

            xTeleport = row; yTeleport = column + rightMostWall[row][column] - 1;
            updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);

            xTeleport = row - topMostWall[row][column] + 1; yTeleport = column;
            updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);

            xTeleport = row + bottomMostWall[row][column] - 1; yTeleport = column;
            updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);
        }
    };

    buildDistance();
}

void printAnswer() {
    cout << distances[cakeCoordinate.first][cakeCoordinate.second] <<'\n';
}

int main() {
    fastIO();
    Read();

    calculate();
    printAnswer();

    return 0;
}

Subtask #1
11.0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	316 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	212 KB	Output is correct
7	Correct	212 KB	Output is correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Correct	320 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	316 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	316 KB	Output is correct
16	Correct	0 ms	316 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	320 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	5 ms	1304 KB	Output is correct
6	Correct	6 ms	1400 KB	Output is correct
7	Correct	6 ms	1288 KB	Output is correct
8	Correct	3 ms	1352 KB	Output is correct

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	324 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	316 KB	Output is correct
4	Correct	0 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	316 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	5 ms	1316 KB	Output is correct
15	Correct	6 ms	1364 KB	Output is correct
16	Correct	6 ms	1408 KB	Output is correct
17	Correct	5 ms	1364 KB	Output is correct
18	Correct	7 ms	1364 KB	Output is correct
19	Correct	7 ms	1364 KB	Output is correct
20	Correct	8 ms	1364 KB	Output is correct
21	Correct	5 ms	1364 KB	Output is correct
22	Correct	5 ms	1360 KB	Output is correct
23	Correct	7 ms	1352 KB	Output is correct
24	Correct	8 ms	1408 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	3 ms	1344 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	316 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	456 KB	Output is correct
14	Correct	6 ms	1312 KB	Output is correct
15	Correct	6 ms	1300 KB	Output is correct
16	Correct	6 ms	1288 KB	Output is correct
17	Correct	5 ms	1356 KB	Output is correct
18	Correct	7 ms	1356 KB	Output is correct
19	Correct	7 ms	1364 KB	Output is correct
20	Correct	7 ms	1364 KB	Output is correct
21	Correct	5 ms	1304 KB	Output is correct
22	Correct	6 ms	1296 KB	Output is correct
23	Correct	6 ms	1296 KB	Output is correct
24	Correct	158 ms	26120 KB	Output is correct
25	Correct	293 ms	26384 KB	Output is correct
26	Correct	225 ms	26172 KB	Output is correct
27	Correct	216 ms	26188 KB	Output is correct
28	Correct	122 ms	26020 KB	Output is correct
29	Correct	131 ms	26020 KB	Output is correct
30	Correct	158 ms	25960 KB	Output is correct
31	Correct	6 ms	1364 KB	Output is correct
32	Correct	219 ms	26080 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	178 ms	26004 KB	Output is correct
36	Correct	0 ms	324 KB	Output is correct
37	Correct	3 ms	1284 KB	Output is correct
38	Correct	75 ms	25928 KB	Output is correct
39	Correct	101 ms	26112 KB	Output is correct

Submission #674450

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 19.0 / 19.0

Subtask #5 30.0 / 30.0

Subtask #1
11.0 / 11.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
19.0 / 19.0

Subtask #5
30.0 / 30.0