Submission #714342

#	Time	Username	Problem	Language	Result	Execution time	Memory
714342		Stickfish	Portals (BOI14_portals)	C++17	100 / 100	725 ms	119072 KiB

portals

#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 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30