oj.uz

Submission #943264

# Submission time Handle Problem Language Result Execution time Memory
943264 2024-03-11T09:45:36 Z salmon Portals (BOI14_portals) C++14
100 / 100
 713 ms 249136 KB 
#include <bits/stdc++.h>
using namespace std;

int R;
int C;
int x,y;
int gx,gy;
int sx,sy;
char c;
int lst[1100][1100];
int nextr[1100][1100];
int nextc[1100][1100];
int prevr[1100][1100];
int prevc[1100][1100];
bool vis[1100][1100];
vector<vector<int>> noom[2100100];
int dw[1100][1100];
int d[1100][1100];


priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
queue<vector<int>> q;

vector<pair<int,int>> bah = {{0,-1},{0,1},{1,0},{-1,0}};

bool valid(int i, int j){
    if(i >= 0 && i < R && 0 <= j && j < C) return true;
    return false;
}

int main(){
    scanf(" %d",&R);
    scanf(" %d",&C);

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            scanf(" %c",&c);
            if(c == '#'){
                lst[i][j] = 1;
            }
            else{
                lst[i][j] = 0;
            }

            if(c == 'C'){
                gx = i;
                gy = j;
            }
            if(c == 'S'){
                sx = i;
                sy = j;
            }

            d[i][j] = -1;
            dw[i][j] = -1;
        }
    }

    for(int i = 0; i < R; i++){
        vector<int> s;

        for(int j = 0; j < C; j++){
            while(!s.empty() && lst[i][j] == 1){
                nextr[i][s.back()] = j;
                s.pop_back();
            }
            s.push_back(j);
        }

        while(!s.empty()){
            nextr[i][s.back()] = C;
            s.pop_back();
        }
    }

    for(int j = 0; j < C; j++){
        vector<int> s;

        for(int i = 0; i < R; i++){
            while(!s.empty() && lst[i][j] == 1){
                nextc[s.back()][j] = i;
                s.pop_back();
            }
            s.push_back(i);
        }

        while(!s.empty()){
            nextc[s.back()][j] = R;
            s.pop_back();
        }
    }


    for(int i = 0; i < R; i++){
        vector<int> s;

        for(int j = C - 1; j >= 0; j--){
            while(!s.empty() && lst[i][j] == 1){
                prevr[i][s.back()] = j;
                s.pop_back();
            }
            s.push_back(j);
        }

        while(!s.empty()){
            prevr[i][s.back()] = -1;
            s.pop_back();
        }
    }

    for(int j = 0; j < C; j++){
        vector<int> s;

        for(int i = R - 1; i >= 0; i--){
            while(!s.empty() && lst[i][j] == 1){
                prevc[s.back()][j] = i;
                s.pop_back();
            }
            s.push_back(i);
        }

        while(!s.empty()){
            prevc[s.back()][j] = -1;
            s.pop_back();
        }
    }

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            if(lst[i][j] == 1) q.push({i,j,0});
        }
    }

    for(int i = 0; i < R; i++){
        q.push({i,0,1});
        q.push({i,C-1,1});
    }

    for(int i = 0; i < C; i++){
        q.push({0,i,1});
        q.push({R-1,i,1});
    }

    while(!q.empty()){
        vector<int> v = q.front();
        q.pop();
        int i = v[0];
        int j = v[1];

        if(dw[i][j] != -1) continue;

        dw[i][j] = v[2];

        for(pair<int,int> ii : bah){
            int ni = ii.first + i;
            int nj = ii.second + j;

            if(valid(ni,nj) && dw[ni][nj] == -1){
                q.push({ni,nj,v[2] + 1});
            }
        }
    }


    noom[0].push_back({0,sx,sy});
    //pq.push({0,sx,sy,false});

    for(int i = 0; i <= R * C; i++){

       for(vector<int> v : noom[i]){
            int i = v[1];
            int j = v[2];
            int de = v[0];

            if(d[i][j] != -1) continue;
            if(lst[i][j] == 1) continue;

            d[i][j] = de;

            for(pair<int,int> ii : bah){
                int ni = ii.first + i;
                int nj = ii.second + j;

                if(valid(ni,nj) && lst[ni][nj] != 1 && d[ni][nj] == -1){
                    noom[de + 1].push_back({de+1,ni,nj});
                }
            }

            if(d[i][prevr[i][j] + 1] == -1) noom[de + dw[i][j]].push_back({de + dw[i][j],i,prevr[i][j] + 1});
            if(d[i][nextr[i][j] - 1] == -1) noom[de + dw[i][j]].push_back({de + dw[i][j],i,nextr[i][j] - 1});
            if(d[prevc[i][j] + 1][j] == -1) noom[de + dw[i][j]].push_back({de + dw[i][j],prevc[i][j] + 1,j});
            if(d[nextc[i][j] - 1][j] == -1) noom[de + dw[i][j]].push_back({de + dw[i][j],nextc[i][j] - 1,j});
       }
       noom[i].clear();
    }

    /*for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            printf("%d ",dw[i][j]);
        }
        printf("\n");
    }*/

    printf("%d",d[gx][gy]);

}
/*
5 4
G#.#
.#.#
...#
S..#
....
*/

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf(" %d",&R);
      |     ~~~~~^~~~~~~~~~
portals.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf(" %d",&C);
      |     ~~~~~^~~~~~~~~~
portals.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |             scanf(" %c",&c);
      |             ~~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 63832 KB Output is correct
2 Correct 14 ms 64092 KB Output is correct
3 Correct 14 ms 64092 KB Output is correct
4 Correct 13 ms 64072 KB Output is correct
5 Correct 13 ms 64344 KB Output is correct
6 Correct 13 ms 64092 KB Output is correct
7 Correct 13 ms 64092 KB Output is correct
8 Correct 13 ms 64080 KB Output is correct
9 Correct 13 ms 63832 KB Output is correct
10 Correct 13 ms 63832 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 63836 KB Output is correct
2 Correct 13 ms 64096 KB Output is correct
3 Correct 14 ms 64012 KB Output is correct
4 Correct 13 ms 63836 KB Output is correct
5 Correct 13 ms 64092 KB Output is correct
6 Correct 13 ms 63956 KB Output is correct
7 Correct 14 ms 64092 KB Output is correct
8 Correct 13 ms 63984 KB Output is correct
9 Correct 14 ms 66480 KB Output is correct
10 Correct 15 ms 66648 KB Output is correct
11 Correct 14 ms 66396 KB Output is correct
12 Correct 14 ms 66456 KB Output is correct
13 Correct 14 ms 66648 KB Output is correct
14 Correct 15 ms 64240 KB Output is correct
15 Correct 14 ms 66396 KB Output is correct
16 Correct 13 ms 63836 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 64056 KB Output is correct
2 Correct 13 ms 64092 KB Output is correct
3 Correct 13 ms 64092 KB Output is correct
4 Correct 13 ms 64092 KB Output is correct
5 Correct 28 ms 71396 KB Output is correct
6 Correct 28 ms 71372 KB Output is correct
7 Correct 28 ms 71004 KB Output is correct
8 Correct 25 ms 71260 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63836 KB Output is correct
2 Correct 14 ms 64092 KB Output is correct
3 Correct 13 ms 64092 KB Output is correct
4 Correct 13 ms 63832 KB Output is correct
5 Correct 13 ms 64092 KB Output is correct
6 Correct 13 ms 64108 KB Output is correct
7 Correct 14 ms 64092 KB Output is correct
8 Correct 13 ms 64092 KB Output is correct
9 Correct 14 ms 66248 KB Output is correct
10 Correct 14 ms 66652 KB Output is correct
11 Correct 14 ms 66396 KB Output is correct
12 Correct 14 ms 66396 KB Output is correct
13 Correct 14 ms 66396 KB Output is correct
14 Correct 28 ms 71516 KB Output is correct
15 Correct 27 ms 71372 KB Output is correct
16 Correct 28 ms 71004 KB Output is correct
17 Correct 28 ms 70748 KB Output is correct
18 Correct 30 ms 71004 KB Output is correct
19 Correct 28 ms 71148 KB Output is correct
20 Correct 32 ms 75604 KB Output is correct
21 Correct 27 ms 71516 KB Output is correct
22 Correct 27 ms 71256 KB Output is correct
23 Correct 31 ms 71256 KB Output is correct
24 Correct 25 ms 70748 KB Output is correct
25 Correct 13 ms 64080 KB Output is correct
26 Correct 14 ms 66396 KB Output is correct
27 Correct 13 ms 63972 KB Output is correct
28 Correct 25 ms 71376 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63924 KB Output is correct
2 Correct 14 ms 64032 KB Output is correct
3 Correct 14 ms 64088 KB Output is correct
4 Correct 14 ms 64072 KB Output is correct
5 Correct 14 ms 64108 KB Output is correct
6 Correct 14 ms 64092 KB Output is correct
7 Correct 13 ms 64088 KB Output is correct
8 Correct 14 ms 64340 KB Output is correct
9 Correct 14 ms 66396 KB Output is correct
10 Correct 15 ms 66652 KB Output is correct
11 Correct 14 ms 66396 KB Output is correct
12 Correct 16 ms 66392 KB Output is correct
13 Correct 15 ms 66392 KB Output is correct
14 Correct 27 ms 71512 KB Output is correct
15 Correct 28 ms 71260 KB Output is correct
16 Correct 28 ms 71000 KB Output is correct
17 Correct 28 ms 70896 KB Output is correct
18 Correct 31 ms 70992 KB Output is correct
19 Correct 27 ms 71256 KB Output is correct
20 Correct 35 ms 75700 KB Output is correct
21 Correct 27 ms 71512 KB Output is correct
22 Correct 27 ms 71256 KB Output is correct
23 Correct 28 ms 71260 KB Output is correct
24 Correct 445 ms 145988 KB Output is correct
25 Correct 361 ms 133864 KB Output is correct
26 Correct 604 ms 185028 KB Output is correct
27 Correct 713 ms 249136 KB Output is correct
28 Correct 421 ms 164340 KB Output is correct
29 Correct 423 ms 163524 KB Output is correct
30 Correct 461 ms 161608 KB Output is correct
31 Correct 25 ms 70748 KB Output is correct
32 Correct 326 ms 135248 KB Output is correct
33 Correct 14 ms 63832 KB Output is correct
34 Correct 15 ms 66396 KB Output is correct
35 Correct 300 ms 126608 KB Output is correct
36 Correct 15 ms 63836 KB Output is correct
37 Correct 25 ms 71256 KB Output is correct
38 Correct 378 ms 158820 KB Output is correct
39 Correct 292 ms 168232 KB Output is correct