Submission #1058851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058851		Pekiban	Portals (BOI14_portals)	C++17	100 / 100	367 ms	137808 KiB

portals

    #include <bits/stdc++.h>
     
    using namespace std;
    #define pb push_back
    #define lwb lower_bound
     
    const int N = 2e6, MX = 1e3+5;
    int dx[] = {0, 1};
    int dy[] = {1, 0};
    vector<array<int, 2>> g[N];
    int di[N];
    bool vis[N];
    char a[MX][MX];
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        int R, C;
        cin >> R >> C;
        int XS, YS, XE, YE;
        for (int i = 1; i <= R; ++i) {
            for (int j = 1; j <= C; ++j) {
                cin >> a[i][j];
                if (a[i][j] == 'S') {
                    XS = i, YS = j;
                }
                if (a[i][j] == 'C') {
                    XE = i, YE = j;
                }
            }
        }
        auto ok = [&](int x, int y) {
            return x != 0 && y != 0 && x != R+1 && y != C+1 && a[x][y] != '#';
        };
        auto h = [&](int x, int y) {
            return x * 1001 + y;
        };
        auto add = [&](int x1, int y1, int x2, int y2, int w) { // (x1, y1) ->(w) (x2, y2)
            g[h(x1, y1)].pb({h(x2, y2), w});
        };
        for (int i = 1; i <= R; ++i) {
            for (int j = 1; j <= C; ++j) {
                for (int k = 0; k < 2; ++k) {
                    if (ok(i + dx[k], j + dy[k]) && ok(i, j)) {
                        add(i, j, i + dx[k], j + dy[k], 1);
                        add(i + dx[k], j + dy[k], i, j, 1);
                    }
                }
            }
        }
        vector<int> H[R+1], V[C+1];
     
        for (int i = 1; i <= R; ++i)    H[i].pb(0);
        for (int j = 1; j <= C; ++j)    V[j].pb(0);
     
        for (int i = 1; i <= R; ++i) {
            for (int j = 1; j <= C; ++j) {
                if (a[i][j] == '#') {
                    H[i].pb(j);
                    V[j].pb(i);
                }
            }
        }
     
        for (int i = 1; i <= R; ++i)    H[i].pb(C+1);
        for (int j = 1; j <= C; ++j)    V[j].pb(R+1);
     
        for (int i = 1; i <= R; ++i)    sort(H[i].begin(), H[i].end());
        for (int j = 1; j <= C; ++j)    sort(V[j].begin(), V[j].end());
        for (int i = 1; i <= R; ++i) {
            for (int j = 1; j <= C; ++j) {
                if (a[i][j] == '#') continue;
                int L = *prev(lwb(H[i].begin(), H[i].end(), j));
                int R = *lwb(H[i].begin(), H[i].end(), j);
                int D = *lwb(V[j].begin(), V[j].end(), i);
                int U = *prev(lwb(V[j].begin(), V[j].end(), i));
                int t = min({j - L, R - j, i - U, D - i});
                add(i, j, i, L+1, t);
                add(i, j, i, R-1, t);
                add(i, j, D-1, j, t);
                add(i, j, U+1, j, t);
            }
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({0, h(XS, YS)});
        fill(di, di + N, 1e9);
        di[h(XS, YS)] = 0;
        while (!pq.empty()) {
            auto [d, s] = pq.top();
            pq.pop();
            if (vis[s]) continue;
            vis[s] = 1;
            for (auto [u, w] : g[s]) {
                if (di[u] > w + d) {
                    di[u] = w + d;
                    pq.push({di[u], u});
                }
            }
        }
        // cout << di[h(2, 8)] << '\n';
        // cout << di[h(2, 7)] << '\n';
        cout << di[h(XE, YE)] << '\n';
    }

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:35:31: warning: 'YE' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |             return x * 1001 + y;
      |                               ^
portals.cpp:35:22: warning: 'XE' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |             return x * 1001 + y;
      |                    ~~^~~~~~
portals.cpp:35:22: warning: 'XS' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |             return x * 1001 + y;
      |                    ~~^~~~~~
portals.cpp:35:31: warning: 'YS' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |             return x * 1001 + y;
      |                               ^

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