Submission #198598

#	Time	Username	Problem	Language	Result	Execution time	Memory
198598		dolphingarlic	Portals (BOI14_portals)	C++14	70 / 100	1100 ms	130804 KiB

portals

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

bool open[1002][1002];
int n, m, visited[1002][1002], to_wall[1002][1002];
vector<pair<int, pair<int, int>>> graph[1002][1002];
pair<int, int> src, dest;

inline bool has_wall(int x, int y) {
    return !(open[x - 1][y] && open[x + 1][y] && open[x][y - 1] && open[x][y + 1]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
        char c;
        cin >> c;
        if (c != '#') open[i][j] = true;
        if (c == 'S') src = {i, j};
        if (c == 'C') dest = {i, j};
    }

    FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
        if (open[i - 1][j]) graph[i][j].push_back({1, {i - 1, j}});
        if (open[i + 1][j]) graph[i][j].push_back({1, {i + 1, j}});
        if (open[i][j - 1]) graph[i][j].push_back({1, {i, j - 1}});
        if (open[i][j + 1]) graph[i][j].push_back({1, {i, j + 1}});
    }

    queue<pair<int, int>> q;
    FOR(i, 0, n + 2) FOR(j, 0, m + 2) {
        if (open[i][j] && has_wall(i, j)) {
            to_wall[i][j] = 1;
            q.push({i, j});
        }
    }
    while (q.size()) {
        pair<int, int> curr = q.front();
        q.pop();
        for (pair<int, pair<int, int>> i : graph[curr.first][curr.second]) {
            if (!to_wall[i.second.first][i.second.second]) {
                to_wall[i.second.first][i.second.second] = to_wall[curr.first][curr.second] + 1;
                q.push(i.second);
            }
        }
    }
    
    pair<int, int> bound;
    bool has;
    FOR(i, 0, n + 1) FOR(j, 0, m + 1) {
        if (!open[i][j]) has = false;
        else {
            if (!has) bound = {i, j};
            has = true;
            graph[i][j].push_back({to_wall[i][j], bound});
        }
    }
    FOR(j, 0, m + 1) FOR(i, 0, n + 1) {
        if (!open[i][j]) has = false;
        else {
            if (!has) bound = {i, j};
            has = true;
            graph[i][j].push_back({to_wall[i][j], bound});
        }
    }
    for (int i = n + 1; i; i--) for (int j = m + 1; j; j--) {
        if (!open[i][j]) has = false;
        else {
            if (!has) bound = {i, j};
            has = true;
            graph[i][j].push_back({to_wall[i][j], bound});
        }
    }
    for (int j = m + 1; j; j--) for (int i = n + 1; i; i--) {
        if (!open[i][j]) has = false;
        else {
            if (!has) bound = {i, j};
            has = true;
            graph[i][j].push_back({to_wall[i][j], bound});
        }
    }

    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({-1, src});
    while (pq.size()) {
        int dist = pq.top().first;
        pair<int, int> curr = pq.top().second;
        pq.pop();
        if (!visited[curr.first][curr.second]) {
            visited[curr.first][curr.second] = -dist;
            for (pair<int, pair<int, int>> i : graph[curr.first][curr.second]) {
                pq.push({dist - i.first, i.second});
            }
        }
        if (curr == dest) break;
    }
    cout << visited[dest.first][dest.second] - 1;
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:84:13: warning: 'has' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if (!has) bound = {i, j};
             ^~

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30