Submission #442502

#	Time	Username	Problem	Language	Result	Execution time	Memory
442502		fammo	Portals (BOI14_portals)	C++11	0 / 100	30 ms	53276 KiB

portals

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define rndom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
//#define endl '\n'
//#define int ll
const int  N = 1000 + 20, MOD = 1e9+7,  base =727, inf  = INT_MAX/2;
int r,c, dis[N][N];
string s[N];
vector<pair<pii, int>>adj[N][N], g[N][N];
int G[] = {1,-1,0,0};
int H[] = {0,0,1,-1};
inline void dij(int rx, int ry){
    //cout << "DIJ " << endl;
    priority_queue<pair<int, pii>>st;
    for(int i = 0; i < N; i ++)for(int j = 0; j < N; j ++)dis[i][j] = inf;
    dis[rx][ry]=0;
    st.push({dis[rx][ry], {rx,ry}});
    while(!st.empty()){
        auto p =st.top(); auto pt = p.Y;int d = -p.X; st.pop();
        int x = pt.X, y = pt.Y;
        if(d >dis[x][y])continue;
        //cout << "IN " << x << ' ' << y << ' ' << d << endl;

        for(auto e : g[x][y]){
            auto q = e.X;int w = e.Y;int xx = q.X, yy = q.Y;

            if(dis[x][y] + w < dis[xx][yy]){
                dis[xx][yy] = dis[x][y] + w;//cout << "G " << xx << ' ' << yy << endl;
                st.push({-dis[xx][yy], q});
            }
        }
        for(int k = 0; k < 4; k ++){
            int xx = x+G[k], yy = y+H[k];
            if(xx > -1 && xx < r && yy > -1 && yy < c){

                if(dis[x][y] + 1 < dis[xx][yy]){ //cout << "ADJ " << xx << ' ' << yy << endl;
                    dis[xx][yy] = dis[x][y] + 1;
                    st.push({-dis[xx][yy], {xx,yy}});
                }
            }
        }
       // cout << "_____________________________" << endl;
    }return;
}
int32_t main(){
    fastio;
    ///auto t = clock();
    int sx = 0, sy = 0, fx=  0, fy= 0;
    cin >> r >> c;
    for(int i = 0; i < r; i ++)cin >> s[i];
    for(int i = 0; i < r; i ++){
        int L=0;
        for(int j = 0; j < c; j ++){
            if(s[i][j] == 'S'){sx=i,sy=j;}
            if(s[i][j] == 'C'){fx = i; fy=j;}
            if(s[i][j] == '#') continue;

            if(j == 0 || s[i][j-1] == '#') L = j;
            adj[i][j].pb({{i,L}, j - L});
        }
    }//cout << "LS FINISH" << endl;
    for(int i = 0; i < r; i ++){
        int R=c-1;
        for(int j = c-1; j >-1; j --){
            if(s[i][j] == '#') continue;         //  cout << i << " " << j << " : " ;
            if(j == 0 || s[i][j+1] == '#') R= j; //           cout << R << endl;

            adj[i][j].pb({{i,R}, R-j});
        }
    }
    for(int j = 0; j < c; j ++){
        int U = 0;
        for(int i = 0; i < r; i ++){
            if(s[i][j] == '#')continue;
            if(i == 0 || s[i-1][j] == '#')U=i;
            adj[i][j].pb({{U,j}, i-U});
        }
    }
    for(int j = 0; j < c; j ++){
        int D = r-1;
        for(int i = r-1; i > -1; i --){
            if(s[i][j] == '#')continue;
            if(i == r-1 || s[i+1][j] == '#')D=i;
            adj[i][j].pb({{D,j}, D-i});
        }
    }
    for(int i = 0; i < r; i ++){
        for(int j = 0; j < c; j ++)if(s[i][j]!='#'){
            auto a = adj[i][j][0], b = adj[i][j][1], c = adj[i][j][2], d = adj[i][j][3];
            if(a.X != make_pair(i,j))g[i][j].pb({a.X, min(b.Y,min(c.Y,d.Y))+1});
            if(b.X != make_pair(i,j))g[i][j].pb({b.X, min(a.Y,min(c.Y,d.Y))+1});
            if(c.X != make_pair(i,j))g[i][j].pb({c.X, min(b.Y,min(a.Y,d.Y))+1});
            if(d.X != make_pair(i,j))g[i][j].pb({d.X, min(b.Y,min(c.Y,a.Y))+1});
            adj[i][j].clear();
        }
    }
    dij(sx,sy);
    cout << dis[fx][fy] << endl;
    ///cout << clock() - t << "ms" << endl;
    return 0;

}

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