oj.uz

Submission #1058851

# Submission time Handle Problem Language Result Execution time Memory
1058851 2024-08-14T14:28:37 Z Pekiban Portals (BOI14_portals) C++17
100 / 100
 367 ms 137808 KB 
    #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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55896 KB Output is correct
2 Correct 8 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 9 ms 55900 KB Output is correct
5 Correct 10 ms 56012 KB Output is correct
6 Correct 8 ms 55900 KB Output is correct
7 Correct 8 ms 55808 KB Output is correct
8 Correct 9 ms 55896 KB Output is correct
9 Correct 8 ms 55900 KB Output is correct
10 Correct 8 ms 55900 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55900 KB Output is correct
2 Correct 8 ms 55964 KB Output is correct
3 Correct 8 ms 55796 KB Output is correct
4 Correct 8 ms 55900 KB Output is correct
5 Correct 8 ms 55900 KB Output is correct
6 Correct 8 ms 56012 KB Output is correct
7 Correct 8 ms 55900 KB Output is correct
8 Correct 8 ms 55780 KB Output is correct
9 Correct 8 ms 56320 KB Output is correct
10 Correct 8 ms 56156 KB Output is correct
11 Correct 8 ms 56156 KB Output is correct
12 Correct 8 ms 56156 KB Output is correct
13 Correct 8 ms 56156 KB Output is correct
14 Correct 7 ms 55972 KB Output is correct
15 Correct 8 ms 56152 KB Output is correct
16 Correct 8 ms 55896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55896 KB Output is correct
2 Correct 8 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 7 ms 55984 KB Output is correct
5 Correct 16 ms 60252 KB Output is correct
6 Correct 16 ms 60356 KB Output is correct
7 Correct 18 ms 60508 KB Output is correct
8 Correct 14 ms 60504 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55896 KB Output is correct
2 Correct 8 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 7 ms 55900 KB Output is correct
5 Correct 8 ms 55900 KB Output is correct
6 Correct 8 ms 55900 KB Output is correct
7 Correct 8 ms 55900 KB Output is correct
8 Correct 8 ms 56008 KB Output is correct
9 Correct 9 ms 56288 KB Output is correct
10 Correct 8 ms 56408 KB Output is correct
11 Correct 8 ms 56180 KB Output is correct
12 Correct 8 ms 56156 KB Output is correct
13 Correct 8 ms 56156 KB Output is correct
14 Correct 16 ms 60320 KB Output is correct
15 Correct 17 ms 60380 KB Output is correct
16 Correct 17 ms 60508 KB Output is correct
17 Correct 16 ms 60504 KB Output is correct
18 Correct 18 ms 60764 KB Output is correct
19 Correct 18 ms 61276 KB Output is correct
20 Correct 19 ms 61276 KB Output is correct
21 Correct 16 ms 60352 KB Output is correct
22 Correct 16 ms 60252 KB Output is correct
23 Correct 17 ms 60336 KB Output is correct
24 Correct 17 ms 61276 KB Output is correct
25 Correct 8 ms 55896 KB Output is correct
26 Correct 8 ms 56152 KB Output is correct
27 Correct 8 ms 55900 KB Output is correct
28 Correct 14 ms 60592 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55896 KB Output is correct
2 Correct 8 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 8 ms 55900 KB Output is correct
5 Correct 8 ms 56152 KB Output is correct
6 Correct 8 ms 56152 KB Output is correct
7 Correct 8 ms 55900 KB Output is correct
8 Correct 7 ms 55900 KB Output is correct
9 Correct 9 ms 56156 KB Output is correct
10 Correct 8 ms 56292 KB Output is correct
11 Correct 8 ms 56156 KB Output is correct
12 Correct 8 ms 56156 KB Output is correct
13 Correct 8 ms 56040 KB Output is correct
14 Correct 15 ms 60252 KB Output is correct
15 Correct 16 ms 60360 KB Output is correct
16 Correct 16 ms 60420 KB Output is correct
17 Correct 17 ms 60508 KB Output is correct
18 Correct 18 ms 60764 KB Output is correct
19 Correct 17 ms 61276 KB Output is correct
20 Correct 17 ms 61276 KB Output is correct
21 Correct 17 ms 60252 KB Output is correct
22 Correct 16 ms 60252 KB Output is correct
23 Correct 17 ms 60456 KB Output is correct
24 Correct 258 ms 118100 KB Output is correct
25 Correct 367 ms 137808 KB Output is correct
26 Correct 321 ms 137556 KB Output is correct
27 Correct 306 ms 137556 KB Output is correct
28 Correct 225 ms 110232 KB Output is correct
29 Correct 232 ms 111416 KB Output is correct
30 Correct 273 ms 112488 KB Output is correct
31 Correct 19 ms 61272 KB Output is correct
32 Correct 301 ms 137608 KB Output is correct
33 Correct 8 ms 55896 KB Output is correct
34 Correct 8 ms 56152 KB Output is correct
35 Correct 244 ms 119864 KB Output is correct
36 Correct 8 ms 55900 KB Output is correct
37 Correct 16 ms 60424 KB Output is correct
38 Correct 171 ms 115572 KB Output is correct
39 Correct 166 ms 102524 KB Output is correct