oj.uz

Submission #943250

# Submission time Handle Problem Language Result Execution time Memory
943250 2024-03-11T09:40:04 Z salmon Portals (BOI14_portals) C++14
70 / 100
 1000 ms 88120 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) && dw[ni][nj] == -1){
                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 && d[ni][nj] == -1){
                pq.push({de+1,ni,nj});
            }
        }

        if(d[i][prevr[i][j] + 1] == -1) pq.push({de + dw[i][j],i,prevr[i][j] + 1});
        if(d[i][nextr[i][j] - 1] == -1) pq.push({de + dw[i][j],i,nextr[i][j] - 1});
        if(d[prevc[i][j] + 1][j] == -1) pq.push({de + dw[i][j],prevc[i][j] + 1,j});
        if(d[nextc[i][j] - 1][j] == -1) 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 12636 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 12732 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 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct

Subtask #2
20.0 / 20.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 4 ms 14948 KB Output is correct
10 Correct 5 ms 15212 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 4 ms 14956 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 3 ms 14940 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 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 19 ms 22108 KB Output is correct
6 Correct 22 ms 22076 KB Output is correct
7 Correct 23 ms 21596 KB Output is correct
8 Correct 14 ms 21852 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 1 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 12632 KB Output is correct
9 Correct 4 ms 14944 KB Output is correct
10 Correct 5 ms 15192 KB Output is correct
11 Correct 3 ms 14944 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 19 ms 22308 KB Output is correct
15 Correct 21 ms 22108 KB Output is correct
16 Correct 28 ms 21824 KB Output is correct
17 Correct 24 ms 21568 KB Output is correct
18 Correct 31 ms 21084 KB Output is correct
19 Correct 36 ms 19520 KB Output is correct
20 Correct 59 ms 24048 KB Output is correct
21 Correct 20 ms 22108 KB Output is correct
22 Correct 20 ms 22256 KB Output is correct
23 Correct 22 ms 21852 KB Output is correct
24 Correct 29 ms 19036 KB Output is correct
25 Correct 1 ms 12636 KB Output is correct
26 Correct 3 ms 14940 KB Output is correct
27 Correct 2 ms 12636 KB Output is correct
28 Correct 14 ms 21852 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 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 5 ms 14940 KB Output is correct
10 Correct 5 ms 15196 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 19 ms 22312 KB Output is correct
15 Correct 21 ms 22132 KB Output is correct
16 Correct 24 ms 21596 KB Output is correct
17 Correct 24 ms 21588 KB Output is correct
18 Correct 31 ms 21084 KB Output is correct
19 Correct 33 ms 19520 KB Output is correct
20 Correct 70 ms 24052 KB Output is correct
21 Correct 18 ms 22284 KB Output is correct
22 Correct 20 ms 22108 KB Output is correct
23 Correct 22 ms 21852 KB Output is correct
24 Correct 716 ms 88120 KB Output is correct
25 Correct 769 ms 36692 KB Output is correct
26 Execution timed out 1075 ms 60576 KB Time limit exceeded
27 Halted 0 ms 0 KB -