Submission #920348

#	Time	Username	Problem	Language	Result	Execution time	Memory
920348		phong	Portals (BOI14_portals)	C++17	0 / 100	4 ms	21592 KiB

portals

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 1e3 + 5;
const ll oo = 1e18, base = 311;
const int lg = 38, M =2e2 + 5;
const ll mod = 1e9 + 7;
#define pii pair<ll, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;

int R, C;
char a[nmax][nmax];
pii st, en;
struct node{
    int w, x, y, msk;
    friend bool operator < (const node &a, const node &b){
        return a.w > b.w;
    }
};
priority_queue<node> q;
int dp[nmax][nmax][5], pos[nmax][nmax][4];
pii get(int i, int j, int k){
    if(k == 0) return { i, pos[i][j][0]};
    if(k == 1) return { i, pos[i][j][1]};
    if(k == 2) return { pos[i][j][2], j};
    if(k == 3) return { pos[i][j][3], j};
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void bfs(){
    memset(dp, 0x3f, sizeof dp);
//    for(int t = 0; t < 3; ++t){
        q.push({0, st.fi, st.se, 0});
        dp[st.fi][st.se][0] = 0;
//    }
    while(q.size()){
        node tmp = q.top();q.pop();
        int i = tmp.x, j = tmp.y, st = tmp.msk;
        if(st == 0 || st == 2){
            for(int k = 0; k < 4; ++k){
                int x = dx[k] + i;
                int y = dy[k] + j;
                if(x >= 1 && x <= R && y >= 1 && y <= C && a[x][y] != '#' && dp[x][y][st] > dp[i][j][st] + 1){
                    dp[x][y][st] = dp[i][j][st] + 1;
                    q.push({dp[x][y][st], x, y, st});
                }
            }
        }
        if(st == 1){
            for(int k = 0; k < 4; ++k){
                int x = get(i, j, k).fi;
                int y = get(i, j, k).se;
                int new_st;
                if(x >= 1 && x <= R && y >= 1 && y <= C && a[x][y] != '#' && dp[x][y][st] > dp[i][j][st] + 1){
                    dp[x][y][st] = dp[i][j][st] + 1;
                    q.push({dp[x][y][st], x, y, st});
                }
            }
        }
        for(int e = st; e < 3; ++e){
            if(dp[i][j][e] > dp[i][j][st]){
                dp[i][j][e] = dp[i][j][st];
                q.push({dp[i][j][e], i, j, e});
            }
        }


    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> R >> C;
    for(int i = 1; i <= R; ++i){
        for(int j = 1; j <= C; ++j){
            cin >> a[i][j];
            if(a[i][j] == 'S') st = {i, j};
            if(a[i][j] == 'C') en = {i, j};
        }
    }
    for(int i = 1; i <= R; ++i){
        for(int j = 1; j <= C; ++j){
            auto &cur = pos[i][j][0];
            cur = j - 1;
            while(cur > 0 && a[i][cur] != '#') cur = pos[i][cur][0];
        }
        for(int j = C; j >= 1; --j){
            auto &cur = pos[i][j][1];
            cur = j + 1;
            while(cur <= C && a[i][cur] != '#') cur = pos[i][cur][1];
        }
    }
    for(int j = 1; j <= C; ++j){
        for(int i = 1; i <= R; ++i){
            auto &cur = pos[i][j][2];
            cur = i - 1;
            while(cur > 0 && a[cur][j] != '#') cur = pos[cur][j][2];
        }
        for(int i = R; i >= 1; --i){
            auto &cur = pos[i][j][3];
            cur = i + 1;
            while(cur <= R && a[cur][j] != '#') cur = pos[cur][j][3];
        }
    }
    for(int i= 1; i <= C; ++i){
        for(int j = 1; j <= R; ++j){
            pos[i][j][0]++;
            pos[i][j][2]++;
            pos[i][j][1]--;
            pos[i][j][3]--;
        }
    }
    bfs();
    cout << dp[en.fi][en.se][2];
}
/*
5 2
3 2
2 5
3 4
3 1

*/

Compilation message (stderr)

portals.cpp: In function 'void bfs()':
portals.cpp:12:12: warning: narrowing conversion of 'st.std::pair<long long int, int>::first' from 'long long int' to 'int' [-Wnarrowing]
   12 | #define fi first
      |            ^
portals.cpp:39:23: note: in expansion of macro 'fi'
   39 |         q.push({0, st.fi, st.se, 0});
      |                       ^~
portals.cpp:59:21: warning: unused variable 'new_st' [-Wunused-variable]
   59 |                 int new_st;
      |                     ^~~~~~
portals.cpp: At global scope:
portals.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~
portals.cpp: In function 'std::pair<long long int, int> get(int, int, int)':
portals.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^

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