Submission #920373

#	Time	Username	Problem	Language	Result	Execution time	Memory
920373		phong	Portals (BOI14_portals)	C++17	20 / 100	5 ms	10840 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;
    friend bool operator < (const node &a, const node &b){
        return a.w > b.w;
    }
};
priority_queue<node> q;
int dp[nmax][nmax], pos[nmax][nmax][4];
node get(int i, int j, int k){
    if(k == 0) return {1,i, pos[i][j][0]};
    if(k == 1) return {1, i, pos[i][j][1]};
    if(k == 2) return {1, pos[i][j][2], j};
    if(k == 3) return {1, pos[i][j][3], j};
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void bfs(){
    memset(dp, 0x3f, sizeof dp);
    q.push({0, st.fi, st.se});
    dp[st.fi][st.se] = 0;
    while(q.size()){
        node tmp = q.top();q.pop();
        int i = tmp.x, j = tmp.y;
        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] > dp[i][j] + 1){
                dp[x][y] = dp[i][j] + 1;
                q.push({dp[x][y], x, y});
            }
        }
        for(int k = 0; k < 4; ++k){
            int x = get(i, j, k).x;
            int y = get(i, j, k).y;
            int w = get(i, j, k).w;
//            cerr << w <<" ";
            if(x >= 1 && x <= R && y >= 1 && y <= C && a[x][y] != '#' && dp[x][y] > dp[i][j] + w){
//                if(i == 4 && j == 3) cout << x << ' ' << y << ' ' << dp[i][j] << ' ' << w << "\n";
                dp[x][y] = dp[i][j] + w;
                q.push({dp[x][y], x, y});
            }
        }
    }
}
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 <= R; ++i){
        for(int j = 1; j <= C; ++j){
            pos[i][j][0]++;
            pos[i][j][2]++;
            pos[i][j][1]--;
            pos[i][j][3]--;
        }
    }
    bfs();
    cout << dp[en.fi][en.se];
}
/*
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:38:19: note: in expansion of macro 'fi'
   38 |     q.push({0, st.fi, st.se});
      |                   ^~
portals.cpp: At global scope:
portals.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main(){
      | ^~~~
portals.cpp: In function 'node 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: 20 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30