oj.uz

Submission #943238

# Submission time Handle Problem Language Result Execution time Memory
943238 2024-03-11T09:34:27 Z salmon Portals (BOI14_portals) C++14
70 / 100
 1000 ms 143800 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];

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)){
                q.push({ni,nj,v[2] + 1});
            }
        }
    }


    pq.push({0,sx,sy});
    //pq.push({0,sx,sy,false});

    while(!pq.empty()){
        vector<int> v = pq.top();
        pq.pop();

        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){
                pq.push({de+1,ni,nj});
            }
        }



        pq.push({de + dw[i][j],i,prevr[i][j] + 1});
        pq.push({de + dw[i][j],i,nextr[i][j] - 1});
        pq.push({de + dw[i][j],prevc[i][j] + 1,j});
        pq.push({de + dw[i][j],nextc[i][j] - 1,j});
    }

    /*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:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf(" %d",&R);
      |     ~~~~~^~~~~~~~~~
portals.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf(" %d",&C);
      |     ~~~~~^~~~~~~~~~
portals.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |             scanf(" %c",&c);
      |             ~~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12704 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 8 ms 15196 KB Output is correct
10 Correct 9 ms 15224 KB Output is correct
11 Correct 5 ms 15196 KB Output is correct
12 Correct 5 ms 15196 KB Output is correct
13 Correct 5 ms 15316 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 5 ms 15196 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 49 ms 24172 KB Output is correct
6 Correct 45 ms 24408 KB Output is correct
7 Correct 50 ms 24668 KB Output is correct
8 Correct 41 ms 24924 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 7 ms 15196 KB Output is correct
10 Correct 7 ms 15192 KB Output is correct
11 Correct 4 ms 15312 KB Output is correct
12 Correct 5 ms 15196 KB Output is correct
13 Correct 5 ms 15448 KB Output is correct
14 Correct 35 ms 24156 KB Output is correct
15 Correct 44 ms 24412 KB Output is correct
16 Correct 50 ms 24920 KB Output is correct
17 Correct 49 ms 23388 KB Output is correct
18 Correct 67 ms 23388 KB Output is correct
19 Correct 111 ms 22224 KB Output is correct
20 Correct 109 ms 25332 KB Output is correct
21 Correct 35 ms 24152 KB Output is correct
22 Correct 40 ms 24152 KB Output is correct
23 Correct 45 ms 24156 KB Output is correct
24 Correct 100 ms 21508 KB Output is correct
25 Correct 2 ms 12632 KB Output is correct
26 Correct 5 ms 15196 KB Output is correct
27 Correct 2 ms 12636 KB Output is correct
28 Correct 25 ms 24924 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12740 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 7 ms 15192 KB Output is correct
10 Correct 7 ms 15196 KB Output is correct
11 Correct 4 ms 15196 KB Output is correct
12 Correct 5 ms 15196 KB Output is correct
13 Correct 5 ms 15196 KB Output is correct
14 Correct 36 ms 24016 KB Output is correct
15 Correct 46 ms 24396 KB Output is correct
16 Correct 56 ms 24868 KB Output is correct
17 Correct 51 ms 23384 KB Output is correct
18 Correct 67 ms 23384 KB Output is correct
19 Correct 109 ms 22260 KB Output is correct
20 Correct 109 ms 25080 KB Output is correct
21 Correct 35 ms 24156 KB Output is correct
22 Correct 39 ms 24276 KB Output is correct
23 Correct 45 ms 24156 KB Output is correct
24 Execution timed out 1076 ms 143800 KB Time limit exceeded
25 Halted 0 ms 0 KB -