Submission #394848

#	Time	Username	Problem	Language	Result	Execution time	Memory
394848		Sara	Portals (BOI14_portals)	C++14	0 / 100	15 ms	24012 KiB

portals

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define F first
#define S second
#define pb push_back
#define md ((b + e) >> 1)

const ll N = 1000 + 3;
const ll LOG = 17;
const ll INF = 1e9 + 5;
const ll MOD = 1e9 + 7;

int n, m;
string s;
bool A[N][N];
int id[N][N], ind = 1;

vector < pair <int, int> > g[N * N];
pair <int, int> st, en;

int le[N][N], ri[N][N];
int up[N][N], dw[N][N];

inline void pre(){
    for (int i = 0; i <= n + 1; i ++){
        for (int j = 0; j <= m + 1; j ++){
            if (A[i][j]){
                le[i][j] = j;
                up[i][j] = i;
            }
            else {
                le[i][j] = le[i][j - 1];
                up[i][j] = up[i - 1][j];
            }
        }
    }
    for (int i = n + 1; i >= 0; i --){
        for (int j = m + 1; j >= 0; j --){
            if (A[i][j]){
                ri[i][j] = j;
                dw[i][j] = i;
            }
            else {
                ri[i][j] = ri[i][j + 1];
                dw[i][j] = dw[i + 1][j];
            }
        }
    }
    return;
}

int dis[N * N];
inline void add_edges(){
    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            if (A[i][j]) continue;
            int w = min({j - le[i][j], ri[i][j] - j, i - up[i][j], dw[i][j] - i});
            int x, y;
            x = i, y = le[i][j] + 1;
            if (!A[x][y]){
              g[id[i][j]].pb({id[x][y], w});
            }
            x = i, y = ri[i][j] - 1;
            if (!A[x][y]){
              g[id[i][j]].pb({id[x][y], w});
            }
            x = up[i][j] + 1, y = j;
            if (!A[x][y]){
                g[id[i][j]].pb({id[x][y], w});
            }
            x = dw[i][j] - 1, y = j;
            if (!A[x][y]){
                g[id[i][j]].pb({id[x][y], w});
            }
            if (!A[i][j - 1]){
                g[id[i][j]].pb({id[i][j - 1], 1});
            }
            if (!A[i][j + 1]){
                g[id[i][j]].pb({id[i][j - 1], 1});
            }
            if (!A[i - 1][j]){
                g[id[i][j]].pb({id[i - 1][j], 1});
            }
            if (!A[i + 1][j]){
                g[id[i][j]].pb({id[i + 1][j], 1});
            }
        }
    }
    return;
}

bool mark[N * N];
priority_queue < pair <int, int> > pq;
inline void dij(){
    for (int i = 0; i <= n + 1; i ++){
        for (int j = 0; j <= m + 1; j ++){
            dis[id[i][j]] = INF;
        }
    }
    dis[id[st.F][st.S]] = 0;
    pq.push({0, id[st.F][st.S]});
    while (pq.size()){
        int v = pq.top().S;
        pq.pop();
        if (mark[v]) continue;
        mark[v] = 1;
        for (auto it : g[v]){
            ll w = it.S;
            auto u = it.F;
            if (dis[v] + w < dis[u]){
                dis[u] = dis[v] + w;
                pq.push({-dis[u], u});
            }
        }
    }
    cout << dis[id[en.F][en.S]] << '\n';
    return;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            cin >> s; s = ' ' + s;
            if (s[j] == 'S'){
                st = {i, j};
            }
            else if (s[j] == 'C'){
                en = {i, j};
            }
            A[i][j] = (s[j] == '#');
        }
    }
    for (int i = 0; i <= n + 1; i ++){
        A[i][0] = A[i][m + 1] = 1;
    }
    for (int j = 0; j <= m + 1; j ++){
        A[0][j] = A[n + 1][j] = 1;
    }
    for (int i = 0; i <= n +1 ; i ++){
        for (int j = 0; j <= m + 1; j ++){
            id[i][j] = ind; 
            ind ++;
        }
    }
    pre();
    add_edges();
    dij();
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30