Submission #499464

#	Time	Username	Problem	Language	Result	Execution time	Memory
499464		Lobo	Portals (BOI14_portals)	C++17	100 / 100	667 ms	92728 KiB

portals

#include<bits/stdc++.h>
using namespace std;

/*for ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
*/

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 1100

ii n, m, a[maxn][maxn], d[maxn][maxn], dp[maxn][maxn];
ii dx[] = {0,0,1,-1};
ii dy[] = {1,-1,0,0};
vector<pair<ii,ii>> wall[maxn][maxn];

void msbfs() {
    queue<pair<ii,ii>> q;
    for(ii i = 0; i <= n+1; i++) {
        for(ii j = 0; j <= m+1; j++) {
            if(a[i][j] == 0) {
                q.push(mp(i,j));
                dp[i][j] = 0;
            }
            else {
                dp[i][j] = INFii;
            }
        }
    }

    while(q.size()) {
        ii x = q.front().fr;
        ii y = q.front().sc;   
        q.pop();

        for(ii i = 0; i < 4; i++) {
            ii x1 = x+dx[i];
            ii y1 = y+dy[i];

            if(x1 == -1 || x1 == n+2 || y1 == -1 || y1 == m+2) continue;


            if(dp[x1][y1] > dp[x][y]+1) {
                dp[x1][y1] = dp[x][y]+1;
                q.push(mp(x1,y1));
            }
        }
    }
}

void shortp(ii sx, ii sy) {
    for(ii i = 0; i <= n+1; i++) {
        for(ii j = 0; j <= m+1; j++) {
            d[i][j] = INFii;
        }
    }

    d[sx][sy] = 0;
    priority_queue<pair<ii,pair<ii,ii>>> pq;
    pq.push(mp(0,mp(sx,sy)));

    while(pq.size()) {
        ii x = pq.top().sc.fr;
        ii y = pq.top().sc.sc;
        ii dist = -pq.top().fr;
        pq.pop();

        if(d[x][y] != dist) continue;

        //adj
        for(ii i = 0; i < 4; i++) {
            ii x1 = x+dx[i];
            ii y1 = y+dy[i];

            if(x1 == -1 || x1 == n+2 || y1 == -1 || y1 == m+2 || a[x1][y1] == 0) continue;

            if(d[x1][y1] > d[x][y]+1) {
                d[x1][y1] = d[x][y]+1;
                pq.push(mp(-d[x1][y1],mp(x1,y1)));
            }
        }

        //wall
        for(auto X : wall[x][y]) {
            ii x1 = X.fr;
            ii y1 = X.sc;

            if(d[x1][y1] > d[x][y]+dp[x][y]) {
                d[x1][y1] = d[x][y]+dp[x][y];
                pq.push(mp(-d[x1][y1],mp(x1,y1)));
            }
        }
    }
}

void solve() {
    cin >> n >> m;

    pair<ii,ii> S, C;

    for(ii i = 1; i <= n; i++) {
        string s; cin >> s;
        for(ii j = 1; j <= m; j++) {
            if(s[j-1] == '#') {
                a[i][j] = 0;
            }
            else {
                a[i][j] = 1;
            }

            if(s[j-1] == 'S') {
                S = mp(i,j);
            }
            if(s[j-1] == 'C') {
                C = mp(i,j);
            }
        }
    }

    //left
    for(ii i = 1; i <= n; i++) {
        pair<ii,ii> act = mp(-1,0);
        for(ii j = 1; j <= m; j++) {
            if(a[i][j] == 0) {
                act.fr = -1;
                continue;
            }

            if(act.fr == -1) {
                act = mp(i,j);
            }

            wall[i][j].pb(act);
        }
    }

    //right
    for(ii i = 1; i <= n; i++) {
        pair<ii,ii> act = mp(-1,0);
        for(ii j = m; j >= 1; j--) {
            if(a[i][j] == 0) {
                act.fr = -1;
                continue;
            }

            if(act.fr == -1) {
                act = mp(i,j);
            }

            wall[i][j].pb(act);
        }
    }

    //up
    for(ii j = 1; j <= m; j++) {
        pair<ii,ii> act = mp(-1,0);
        for(ii i = 1; i <= n; i++) {
            if(a[i][j] == 0) {
                act.fr = -1;
                continue;
            }

            if(act.fr == -1) {
                act = mp(i,j);
            }

            wall[i][j].pb(act);
        }
    }

    //down
    for(ii j = 1; j <= m; j++) {
        pair<ii,ii> act = mp(-1,0);
        for(ii i = n; i >= 1; i--) {
            if(a[i][j] == 0) {
                act.fr = -1;
                continue;
            }

            if(act.fr == -1) {
                act = mp(i,j);
            }

            wall[i][j].pb(act);
        }
    }

    msbfs();
    shortp(S.fr,S.sc);

    // for(ii i = 0; i <= n+1; i++) {
    //     for(ii j = 0; j <= m+1; j++) {
    //         cout << dp[i][j] << " ";
    //     }cout << endl;
    // }

    cout << d[C.fr][C.sc] << endl;

}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    ii tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

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