oj.uz

Submission #829796

# Submission time Handle Problem Language Result Execution time Memory
829796 2023-08-18T15:05:41 Z BidoTeima Portals (BOI14_portals) C++17
100 / 100
 861 ms 207508 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int nearest_wall[N][N];
vector<array<int,3>>adj[N][N];
vector<int>walls_x[N],walls_y[N];
char grid[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int r,c;
bool check(int x, int y){
    return x>=1&&y>=1&&x<=r&&y<=c&&grid[x][y]!='#';
}
int main()
{ 
    memset(nearest_wall,0xf3f3f,sizeof(nearest_wall));
    cin>>r>>c; 
    int stx,sty,endx,endy;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            cin>>grid[i][j];
            if(grid[i][j]=='S')stx=i,sty=j;
            if(grid[i][j]=='C')endx=i,endy=j;
        }
    }
    queue<vector<int>>q;
    for(int i = 0; i <= r + 1; i++){
        grid[i][c+1]='#';
        grid[i][0]='#';
    }
    for(int i = 0; i <= c + 1; i++){
        grid[r+1][i]='#';
        grid[0][i]='#';
    }
    for(int i = 0; i <= r + 1; i++){
        for(int j = 0; j <= c + 1; j++){
            if(grid[i][j]!='#'){
                for(int k = 0; k < 4; k++){
                    if(check(i+dx[k],j+dy[k])){
                        adj[i][j].push_back({i+dx[k],j+dy[k],1});
                    }
                }
            }
            else{
                walls_x[i].push_back(j);
                walls_y[j].push_back(i);
                q.push({i, j, 0}); 
            }
        }
    }
    for(int i = 0; i <= r+1; i++)sort(walls_x[i].begin(),walls_x[i].end());
    for(int i = 0; i <= c+1; i++)sort(walls_y[i].begin(),walls_y[i].end());
    while(!q.empty()){
        int x = q.front()[0];
        int y = q.front()[1];
        int d = q.front()[2];
        q.pop();
        if(nearest_wall[x][y]<2e6)continue;
        nearest_wall[x][y]=d;
        for(int i = 0; i < 4; i++){
            if(x+dx[i]>=0&&x+dx[i]<=r+1&&y+dy[i]>=0&&y+dy[i]<=c+1){
                q.push({x+dx[i],y+dy[i],d+1});
            }
        }
    }
    for(int x = 0; x <= r+1; x++){
        for(int y = 0; y <= c+1; y++){ 
            if(grid[x][y]=='#')continue;
            // nearest wall to the left (<y)
            auto it = lower_bound(walls_x[x].begin(), walls_x[x].end(), y);
            if(it != walls_x[x].begin()){
                it = prev(it);
                adj[x][y].push_back({x, *it + 1, nearest_wall[x][y]});
            }
            // nearest wall to the right (>y)
            it = upper_bound(walls_x[x].begin(), walls_x[x].end(), y);
            if(it != walls_x[x].end()){
                adj[x][y].push_back({x, *it - 1, nearest_wall[x][y]});
            }
            // nearest wall down (<x)
            it = lower_bound(walls_y[y].begin(), walls_y[y].end(), x);
            if(it != walls_y[y].begin()){
                it = prev(it);
                adj[x][y].push_back({*it + 1, y, nearest_wall[x][y]});
            }
            // nearest wall up (>x)
            it = upper_bound(walls_y[y].begin(), walls_y[y].end(), x);
            if(it != walls_y[y].end()){
                adj[x][y].push_back({*it - 1, y, nearest_wall[x][y]});
            }
        }
    }
    using a3 = array<int,3>;
    priority_queue<a3,vector<a3>,greater<a3>>pq;
    pq.push({0,stx,sty});
    int dist[N][N];
    memset(dist,0xf3f3f,sizeof(dist));
    dist[stx][sty]=0;
    while(!pq.empty()){
        int x = get<1>(pq.top());
        int y = get<2>(pq.top());
        int d = get<0>(pq.top());
        pq.pop();
        if(dist[x][y]!=d)continue;
        for(auto&edge:adj[x][y]){
            int nx=edge[0],ny=edge[1];
            if(d + edge[2] < dist[nx][ny]){
                dist[nx][ny]=d+edge[2];
                pq.push({dist[nx][ny],nx,ny});
            }
        }
    }
    cout<<dist[endx][endy];
    return 0;
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:113:26: warning: 'endy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     cout<<dist[endx][endy];
      |                          ^
portals.cpp:113:26: warning: 'endx' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:98:19: warning: 'sty' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     dist[stx][sty]=0;
      |     ~~~~~~~~~~~~~~^~
portals.cpp:98:19: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31944 KB Output is correct
2 Correct 14 ms 31956 KB Output is correct
3 Correct 17 ms 31908 KB Output is correct
4 Correct 16 ms 31920 KB Output is correct
5 Correct 13 ms 31972 KB Output is correct
6 Correct 13 ms 31956 KB Output is correct
7 Correct 14 ms 31928 KB Output is correct
8 Correct 14 ms 31956 KB Output is correct
9 Correct 16 ms 31956 KB Output is correct
10 Correct 14 ms 31956 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31956 KB Output is correct
2 Correct 13 ms 31956 KB Output is correct
3 Correct 13 ms 31956 KB Output is correct
4 Correct 13 ms 31988 KB Output is correct
5 Correct 13 ms 31956 KB Output is correct
6 Correct 14 ms 32020 KB Output is correct
7 Correct 17 ms 31904 KB Output is correct
8 Correct 14 ms 31956 KB Output is correct
9 Correct 19 ms 32340 KB Output is correct
10 Correct 15 ms 32276 KB Output is correct
11 Correct 15 ms 32468 KB Output is correct
12 Correct 16 ms 32468 KB Output is correct
13 Correct 16 ms 32468 KB Output is correct
14 Correct 16 ms 31956 KB Output is correct
15 Correct 18 ms 32276 KB Output is correct
16 Correct 17 ms 31972 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31904 KB Output is correct
2 Correct 16 ms 31948 KB Output is correct
3 Correct 16 ms 31892 KB Output is correct
4 Correct 14 ms 31956 KB Output is correct
5 Correct 36 ms 38460 KB Output is correct
6 Correct 38 ms 38836 KB Output is correct
7 Correct 37 ms 39460 KB Output is correct
8 Correct 30 ms 39124 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31956 KB Output is correct
2 Correct 13 ms 31920 KB Output is correct
3 Correct 13 ms 31956 KB Output is correct
4 Correct 15 ms 31992 KB Output is correct
5 Correct 14 ms 31900 KB Output is correct
6 Correct 14 ms 32020 KB Output is correct
7 Correct 17 ms 32004 KB Output is correct
8 Correct 14 ms 32016 KB Output is correct
9 Correct 16 ms 32284 KB Output is correct
10 Correct 16 ms 32316 KB Output is correct
11 Correct 17 ms 32392 KB Output is correct
12 Correct 16 ms 32432 KB Output is correct
13 Correct 16 ms 32468 KB Output is correct
14 Correct 35 ms 38388 KB Output is correct
15 Correct 38 ms 38720 KB Output is correct
16 Correct 46 ms 39440 KB Output is correct
17 Correct 36 ms 38148 KB Output is correct
18 Correct 39 ms 38476 KB Output is correct
19 Correct 34 ms 36620 KB Output is correct
20 Correct 32 ms 36564 KB Output is correct
21 Correct 44 ms 38600 KB Output is correct
22 Correct 39 ms 38516 KB Output is correct
23 Correct 37 ms 38808 KB Output is correct
24 Correct 33 ms 36492 KB Output is correct
25 Correct 14 ms 31880 KB Output is correct
26 Correct 16 ms 32340 KB Output is correct
27 Correct 15 ms 31952 KB Output is correct
28 Correct 32 ms 39148 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31984 KB Output is correct
2 Correct 14 ms 31928 KB Output is correct
3 Correct 14 ms 31956 KB Output is correct
4 Correct 14 ms 31992 KB Output is correct
5 Correct 14 ms 31956 KB Output is correct
6 Correct 17 ms 31956 KB Output is correct
7 Correct 14 ms 31956 KB Output is correct
8 Correct 15 ms 31932 KB Output is correct
9 Correct 16 ms 32340 KB Output is correct
10 Correct 16 ms 32308 KB Output is correct
11 Correct 16 ms 32372 KB Output is correct
12 Correct 16 ms 32352 KB Output is correct
13 Correct 15 ms 32468 KB Output is correct
14 Correct 34 ms 38356 KB Output is correct
15 Correct 36 ms 38828 KB Output is correct
16 Correct 37 ms 39352 KB Output is correct
17 Correct 37 ms 38220 KB Output is correct
18 Correct 39 ms 38568 KB Output is correct
19 Correct 34 ms 36564 KB Output is correct
20 Correct 34 ms 36592 KB Output is correct
21 Correct 37 ms 38600 KB Output is correct
22 Correct 37 ms 38476 KB Output is correct
23 Correct 39 ms 38860 KB Output is correct
24 Correct 861 ms 184088 KB Output is correct
25 Correct 639 ms 143128 KB Output is correct
26 Correct 622 ms 142908 KB Output is correct
27 Correct 583 ms 142800 KB Output is correct
28 Correct 751 ms 185364 KB Output is correct
29 Correct 829 ms 189204 KB Output is correct
30 Correct 840 ms 192084 KB Output is correct
31 Correct 34 ms 36564 KB Output is correct
32 Correct 580 ms 143616 KB Output is correct
33 Correct 16 ms 31956 KB Output is correct
34 Correct 16 ms 32252 KB Output is correct
35 Correct 561 ms 132136 KB Output is correct
36 Correct 14 ms 31944 KB Output is correct
37 Correct 33 ms 39252 KB Output is correct
38 Correct 639 ms 207508 KB Output is correct
39 Correct 579 ms 166208 KB Output is correct