Submission #1058851

#TimeUsernameProblemLanguageResultExecution timeMemory
1058851PekibanPortals (BOI14_portals)C++17
100 / 100
367 ms137808 KiB
#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;
      |                               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...