oj.uz

Submission #714342

# Submission time Handle Problem Language Result Execution time Memory
714342 2023-03-24T09:20:22 Z Stickfish Portals (BOI14_portals) C++17
100 / 100
 725 ms 119072 KB 
#include <iostream>
#include <bitset>
#include <cassert>
#include <queue>
using namespace std;

const int MAXN = 1024;
bitset<MAXN> f[MAXN];
vector<pair<int, int>> ondir[MAXN][MAXN];

bool getf(pair<int, int> pt) {
    if (pt.first < 0 || pt.second < 0)
        return 0;
    return f[pt.first][pt.second];
}

vector<pair<int, int>> get_adj(pair<int, int> pt) {
    vector<pair<int, int>> ans;
    ans.push_back({pt.first - 1, pt.second});
    ans.push_back({pt.first + 1, pt.second});
    ans.push_back({pt.first, pt.second + 1});
    ans.push_back({pt.first, pt.second - 1});
    return ans;
}

int walldepth[MAXN][MAXN];
void get_walldepth(int n, int m) {
    queue<pair<int, int>> q;
    for (int i = 0; i <= n + 1; ++i) {
        for (int j = 0; j <= m + 1; ++j) {
            if (f[i][j]) {
                walldepth[i][j] = MAXN * MAXN;
            } else {
                q.push({i, j});
            }
        }
    }
    while (q.size()) {
        pair<int, int> v = q.front();
        q.pop();
        for (auto u : get_adj(v)) {
            if (getf(u) && walldepth[u.first][u.second] > walldepth[v.first][v.second] + 1) {
                walldepth[u.first][u.second] = walldepth[v.first][v.second] + 1;
                q.push(u);
            }
        }
    }
}

void get_ondir(pair<int, int> st, pair<int, int> ed, pair<int, int> mv) {
    bool prevwall = true;
    pair<int, int> val;
    for (pair<int, int> v = st; v != ed; v = pair<int, int>(v.first + mv.first, v.second + mv.second)) {
        if (!getf(v)) {
            prevwall = true;
            continue;
        }
        if (prevwall) {
            prevwall = false;
            val = v;
        }
        ondir[v.first][v.second].push_back(val);
    }
}

int get_dist(pair<int, int> a, pair<int, int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

int depth[MAXN][MAXN];
vector<pair<int, int>> rdepth[MAXN * MAXN];
void bfs(pair<int, int> st, int n, int m) {
    for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j) {
        depth[i][j] = MAXN * MAXN - 1;
    }
    depth[st.first][st.second] = 0;
    rdepth[0].push_back(st);
    int curdepth = 0;
    while (curdepth < MAXN * MAXN) {
        if (rdepth[curdepth].empty()) {
            ++curdepth;
            continue;
        }
        pair<int, int> v = rdepth[curdepth].back();
        rdepth[curdepth].pop_back();
        if (depth[v.first][v.second] < curdepth)
            continue;
        for (auto u : get_adj(v)) {
            if (getf(u) && depth[u.first][u.second] > curdepth + 1) {
                depth[u.first][u.second] = curdepth + 1;
                rdepth[curdepth + 1].push_back(u);
            }
        }
        int depdir = curdepth + walldepth[v.first][v.second];
        //if (v.first == 4 && v.second == 3) {
            //for (auto u : ondir[v.first][v.second])
                //cout << u.first << ' ' << u.second << endl;
        //}
        for (auto u : ondir[v.first][v.second]) {
            assert(getf(u));
            if (depth[u.first][u.second] > depdir) {
                depth[u.first][u.second] = depdir;
                rdepth[depdir].push_back(u);
            }
        }
    }
}

signed main() {
    int n, m;
    cin >> n >> m;
    pair<int, int> st;
    pair<int, int> ed;
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; ++j) {
            f[i][j] = s[j - 1] != '#';
            if (s[j - 1] == 'C')
                ed = {i, j};
            if (s[j - 1] == 'S')
                st = {i, j};
        }
    }
    get_walldepth(n, m);
    for (int i = 1; i <= n; ++i) {
        get_ondir({i, 0}, {i, m + 1}, {0, 1});
        get_ondir({i, m + 1}, {i, 0}, {0, -1});
    }
    for (int j = 1; j <= m; ++j) {
        get_ondir({0, j}, {n + 1, j}, {1, 0});
        get_ondir({n + 1, j}, {0, j}, {-1, 0});
    }
    
    bfs(st, n, m);
    //for (int i = 0; i <= n + 1; ++i) {
        //for (int j = 0; j <= m + 1; ++j)
            //cout << depth[i][j] << ' ';
        //cout << endl;
    //}
    cout << depth[ed.first][ed.second] << '\n';
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 49492 KB Output is correct
2 Correct 27 ms 49632 KB Output is correct
3 Correct 28 ms 49620 KB Output is correct
4 Correct 25 ms 49560 KB Output is correct
5 Correct 26 ms 49600 KB Output is correct
6 Correct 27 ms 49620 KB Output is correct
7 Correct 28 ms 49604 KB Output is correct
8 Correct 27 ms 49652 KB Output is correct
9 Correct 26 ms 49560 KB Output is correct
10 Correct 28 ms 49556 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 49512 KB Output is correct
2 Correct 25 ms 49560 KB Output is correct
3 Correct 29 ms 49536 KB Output is correct
4 Correct 26 ms 49512 KB Output is correct
5 Correct 26 ms 49620 KB Output is correct
6 Correct 26 ms 49620 KB Output is correct
7 Correct 29 ms 49620 KB Output is correct
8 Correct 28 ms 49640 KB Output is correct
9 Correct 28 ms 50132 KB Output is correct
10 Correct 33 ms 50076 KB Output is correct
11 Correct 28 ms 50048 KB Output is correct
12 Correct 27 ms 50076 KB Output is correct
13 Correct 30 ms 50004 KB Output is correct
14 Correct 31 ms 49548 KB Output is correct
15 Correct 31 ms 50064 KB Output is correct
16 Correct 27 ms 49516 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 49492 KB Output is correct
2 Correct 30 ms 49596 KB Output is correct
3 Correct 28 ms 49620 KB Output is correct
4 Correct 26 ms 49556 KB Output is correct
5 Correct 42 ms 52548 KB Output is correct
6 Correct 44 ms 52668 KB Output is correct
7 Correct 44 ms 52812 KB Output is correct
8 Correct 44 ms 53300 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49552 KB Output is correct
2 Correct 30 ms 49612 KB Output is correct
3 Correct 29 ms 49620 KB Output is correct
4 Correct 27 ms 49488 KB Output is correct
5 Correct 26 ms 49540 KB Output is correct
6 Correct 28 ms 49612 KB Output is correct
7 Correct 27 ms 49584 KB Output is correct
8 Correct 27 ms 49556 KB Output is correct
9 Correct 31 ms 50132 KB Output is correct
10 Correct 29 ms 50132 KB Output is correct
11 Correct 33 ms 50088 KB Output is correct
12 Correct 29 ms 50004 KB Output is correct
13 Correct 28 ms 50064 KB Output is correct
14 Correct 43 ms 52564 KB Output is correct
15 Correct 43 ms 52612 KB Output is correct
16 Correct 52 ms 52784 KB Output is correct
17 Correct 43 ms 52688 KB Output is correct
18 Correct 46 ms 53004 KB Output is correct
19 Correct 44 ms 53560 KB Output is correct
20 Correct 46 ms 53488 KB Output is correct
21 Correct 42 ms 52588 KB Output is correct
22 Correct 45 ms 52588 KB Output is correct
23 Correct 47 ms 52812 KB Output is correct
24 Correct 47 ms 53504 KB Output is correct
25 Correct 28 ms 49584 KB Output is correct
26 Correct 28 ms 50116 KB Output is correct
27 Correct 28 ms 49568 KB Output is correct
28 Correct 44 ms 53296 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49484 KB Output is correct
2 Correct 27 ms 49572 KB Output is correct
3 Correct 27 ms 49640 KB Output is correct
4 Correct 27 ms 49508 KB Output is correct
5 Correct 27 ms 49620 KB Output is correct
6 Correct 27 ms 49600 KB Output is correct
7 Correct 31 ms 49540 KB Output is correct
8 Correct 27 ms 49640 KB Output is correct
9 Correct 28 ms 50120 KB Output is correct
10 Correct 28 ms 50064 KB Output is correct
11 Correct 30 ms 50004 KB Output is correct
12 Correct 33 ms 49996 KB Output is correct
13 Correct 28 ms 50028 KB Output is correct
14 Correct 43 ms 52624 KB Output is correct
15 Correct 41 ms 52656 KB Output is correct
16 Correct 43 ms 52816 KB Output is correct
17 Correct 44 ms 52760 KB Output is correct
18 Correct 45 ms 53036 KB Output is correct
19 Correct 48 ms 53576 KB Output is correct
20 Correct 46 ms 53572 KB Output is correct
21 Correct 42 ms 52628 KB Output is correct
22 Correct 42 ms 52564 KB Output is correct
23 Correct 43 ms 52636 KB Output is correct
24 Correct 515 ms 99920 KB Output is correct
25 Correct 704 ms 117404 KB Output is correct
26 Correct 666 ms 118892 KB Output is correct
27 Correct 662 ms 118304 KB Output is correct
28 Correct 506 ms 94840 KB Output is correct
29 Correct 510 ms 95112 KB Output is correct
30 Correct 551 ms 95708 KB Output is correct
31 Correct 47 ms 53556 KB Output is correct
32 Correct 725 ms 119072 KB Output is correct
33 Correct 27 ms 49576 KB Output is correct
34 Correct 29 ms 50000 KB Output is correct
35 Correct 611 ms 103304 KB Output is correct
36 Correct 31 ms 49540 KB Output is correct
37 Correct 52 ms 53244 KB Output is correct
38 Correct 578 ms 113396 KB Output is correct
39 Correct 401 ms 87980 KB Output is correct