oj.uz

Submission #861179

# Submission time Handle Problem Language Result Execution time Memory
861179 2023-10-15T15:06:11 Z qwusha Portals (BOI14_portals) C++17
70 / 100
 351 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef long double ld;
const ll inf = 1e9;
const ld eps = 1e-8;



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    int stai, staj, fini, finj;
    vector<vector<char>> a(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'S') {
                stai = i;
                staj = j;
            } else if (a[i][j] == 'C') {
                fini = i;
                finj = j;
            }
        }
    }
    vector<vector<vector<vector<int>>>> g(n, vector<vector<vector<int>>>(m));
    vector<vector<vector<pair<int, int>>>> steni(n, vector<vector<pair<int, int>>>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == '#')
                continue;
            for (int c = 0; c < 4; c++) {
                int ci = (c % 2 == 0) * (c - 1),
                cj = (c % 2 == 1) * (c - 2);
                if (i + ci >= 0 && i + ci < n && j + cj >= 0 && j + cj < m && a[i + ci][j + cj] != '#') {
                    g[i][j].push_back({i + ci, j + cj, 1});
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        pair<int, int> cur = {i, 0};
        for (int j = 0; j < m; j++) {
            if (a[i][j] == '#')
                cur = {i, j + 1};
            else
                steni[i][j].push_back(cur);
        }
        cur = {i, m - 1};
        for (int j = m - 1; j >= 0; j--) {
            if (a[i][j] == '#')
                cur = {i, j - 1};
            else
                steni[i][j].push_back(cur);
        }
    }
    for (int j = 0; j < m; j++) {
        pair<int, int> cur = {0, j};
        for (int i = 0; i < n; i++) {
            if (a[i][j] == '#')
                cur = {i + 1, j};
            else
                steni[i][j].push_back(cur);
        }
        cur = {n - 1, j};
        for (int i = n - 1; i >= 0; i--) {
            if (a[i][j] == '#')
                cur = {i - 1, j};
            else
                steni[i][j].push_back(cur);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 4) {
                int x = 1;
            }
            int mst = inf;
            int inde = -1;
            for (int qw = 0; qw < steni[i][j].size(); qw++) {
                auto [si, sj] = steni[i][j][qw];
                if (abs(si - i) + abs(sj - j) < mst) {
                    mst = abs(si - i) + abs(sj - j);
                    inde = qw;
                }
            }
            for (int qw = 0; qw < steni[i][j].size(); qw++) {
                auto [si, sj] = steni[i][j][qw];
                if (qw != inde && abs(si - i) + abs(sj - j) > mst + 1) {
                    g[i][j].push_back({si, sj, mst + 1});
                }
            }
        }
    }
    vector<vector<pair<int, int>>> par(n, vector<pair<int, int>>(m, {-1, -1}));
    vector<vector<int>> dist(n, vector<int>(m, inf));
    dist[stai][staj] = 0;
    set<vector<int>> st = {{0, stai, staj}};
    while (!st.empty()) {
        auto t = st.begin();
        auto qw = *t;
        int d = qw[0], vi = qw[1], vj = qw[2];
        st.erase(t);
        for (auto vec : g[vi][vj]) {
            int ui = vec[0], uj = vec[1], w = vec[2];
            if (d + w < dist[ui][uj]) {
                par[ui][uj] = {vi, vj};
                st.erase({dist[ui][uj], ui, uj});
                dist[ui][uj] = d + w;
                st.insert({d + w, ui, uj});
            }
        }
    }
    cout << dist[fini][finj] << '\n';
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:81:21: warning: unused variable 'x' [-Wunused-variable]
   81 |                 int x = 1;
      |                     ^
portals.cpp:85:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for (int qw = 0; qw < steni[i][j].size(); qw++) {
      |                              ~~~^~~~~~~~~~~~~~~~~~~~
portals.cpp:92:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for (int qw = 0; qw < steni[i][j].size(); qw++) {
      |                              ~~~^~~~~~~~~~~~~~~~~~~~
portals.cpp:119:28: warning: 'finj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |     cout << dist[fini][finj] << '\n';
      |                            ^
portals.cpp:119:22: warning: 'fini' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |     cout << dist[fini][finj] << '\n';
      |                      ^
portals.cpp:102:20: warning: 'staj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |     dist[stai][staj] = 0;
      |                    ^
portals.cpp:102:14: warning: 'stai' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |     dist[stai][staj] = 0;
      |              ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3 ms 1628 KB Output is correct
10 Correct 3 ms 1628 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 1 ms 348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 19 ms 8320 KB Output is correct
6 Correct 22 ms 9052 KB Output is correct
7 Correct 25 ms 10588 KB Output is correct
8 Correct 14 ms 7516 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3 ms 1628 KB Output is correct
10 Correct 3 ms 1740 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 856 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 18 ms 8124 KB Output is correct
15 Correct 22 ms 9052 KB Output is correct
16 Correct 28 ms 10844 KB Output is correct
17 Correct 26 ms 11608 KB Output is correct
18 Correct 36 ms 15448 KB Output is correct
19 Correct 51 ms 22392 KB Output is correct
20 Correct 48 ms 22252 KB Output is correct
21 Correct 19 ms 8284 KB Output is correct
22 Correct 21 ms 8540 KB Output is correct
23 Correct 22 ms 9308 KB Output is correct
24 Correct 57 ms 22108 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 2 ms 1372 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 14 ms 7516 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 1628 KB Output is correct
10 Correct 3 ms 1628 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 20 ms 8144 KB Output is correct
15 Correct 27 ms 9072 KB Output is correct
16 Correct 25 ms 10584 KB Output is correct
17 Correct 26 ms 11608 KB Output is correct
18 Correct 36 ms 15196 KB Output is correct
19 Correct 61 ms 22616 KB Output is correct
20 Correct 52 ms 22588 KB Output is correct
21 Correct 20 ms 8288 KB Output is correct
22 Correct 20 ms 8544 KB Output is correct
23 Correct 23 ms 9312 KB Output is correct
24 Runtime error 351 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -