Submission #107709

#	Time	Username	Problem	Language	Result	Execution time	Memory
107709		patrikpavic2	Portals (BOI14_portals)	C++17	100 / 100	553 ms	38212 KiB

portals

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <map>
#include <queue>
#include <cstring>

using namespace std;

typedef long long int llint;
typedef pair < int,int> pii;
typedef pair < int , pii > ppii;

const int N = 1005;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int K = 1005;

int px[4] = {0, 0 , 1 , -1};
int py[4] = {1 ,-1 , 0 , 0};

priority_queue < ppii, vector < ppii >, greater < ppii > > st;
int mv[N][N][4][2];
int dis[N][N],n,m;
char s[N][N];

int diss(int x1,int y1,int x2,int y2){
    return abs(x1 - x2) + abs(y1 - y2);
}

void dickstra(int x,int y){
    st.push(make_pair(0,make_pair(x,y)));
    dis[x][y] = 0;
    while(!st.empty()){
        ppii cur = st.top();st.pop();
        int cx = cur.second.first;
        int cy = cur.second.second;
        int t = cur.first;
        for(int i = 0;i<4;i++){
            if(s[cx + px[i]][cy + py[i]] == '#') continue;
            if(dis[cx + px[i]][cy + py[i]] <= t + 1) continue;
            dis[cx + px[i]][cy + py[i]] = t  + 1;
            st.push(make_pair(t + 1, make_pair(cx + px[i], cy + py[i])));
        }

        for(int i = 0;i<4;i++){
            for(int j = 0;j<4;j++){
                if(i == j) continue;
                int ox = mv[cx][cy][i][0];
                int oy = mv[cx][cy][i][1];
                int nx = mv[cx][cy][j][0];
                int ny = mv[cx][cy][j][1];
                int nt = diss(cx, cy, ox, oy) + 1 + t;
                if(nx < 1 || nx > n-2 || ny < 1 || ny > m-2) continue;
                if(cx == nx && cy == ny) continue;
                if(dis[nx][ny] <= nt) continue;
                dis[nx][ny] = nt;
                st.push(make_pair(nt, make_pair(nx, ny)));
            }
        }
    }
}


int main(){
    memset(dis,INF,sizeof(dis));
    scanf("%d%d",&n,&m);
    n += 2, m += 2;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(i > 0 && j > 0 && i + 1 < n && j + 1 < m) scanf(" %c", &s[i][j]);
            else s[i][j] = '#';
        }
    }
    for(int i = 1;i<n-1;i++){
        for(int j = m-2;j>0;j--){
            if(s[i][j] == '#') continue;
            if(s[i][j+1] == '#'){mv[i][j][0][0] = i;mv[i][j][0][1] = j;}
            else{ mv[i][j][0][0] = mv[i][j+1][0][0];mv[i][j][0][1] = mv[i][j+1][0][1];}
        }
    }
    for(int i = 1;i<n-1;i++){
        for(int j = 1;j<m-1;j++){
            if(s[i][j] == '#') continue;
            if(s[i][j-1] == '#'){mv[i][j][1][0] = i;mv[i][j][1][1] = j;}
            else{ mv[i][j][1][0] = mv[i][j-1][1][0];mv[i][j][1][1] = mv[i][j-1][1][1];}
        }
    }
    for(int j = 1;j<m-1;j++){
        for(int i = 1;i<n-1;i++){
            if(s[i][j] == '#') continue;
            if(s[i-1][j] == '#'){mv[i][j][2][0] = i;mv[i][j][2][1] = j;}
            else {mv[i][j][2][0] = mv[i-1][j][2][0];mv[i][j][2][1] = mv[i-1][j][2][1];}
        }
    }
    for(int j = 1;j<m-1;j++){
        for(int i = n-2;i>0;i--){
            if(s[i][j] == '#') continue;
            if(s[i+1][j] == '#'){mv[i][j][3][0] = i;mv[i][j][3][1] = j;}
            else{mv[i][j][3][0] = mv[i+1][j][3][0];mv[i][j][3][1] = mv[i+1][j][3][1];}
        }
    }
    for(int j = 1;j<m-1;j++){
        for(int i = 1;i<n-1;i++){
            if(s[i][j] ==  'S') dickstra(i, j);
        }
    }
    for(int i = 1;i<n-1;i++){
        for(int j = 1;j<m-1;j++){
            if(s[i][j] == 'C'){
                if(dis[i][j] == INF) printf("nemoguce\n");
                else printf("%d ", dis[i][j]);
            }
        }
    }
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
portals.cpp:73:63: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             if(i > 0 && j > 0 && i + 1 < n && j + 1 < m) scanf(" %c", &s[i][j]);
                                                          ~~~~~^~~~~~~~~~~~~~~~~

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