oj.uz

Submission #465738

# Submission time Handle Problem Language Result Execution time Memory
465738 2021-08-16T17:37:54 Z AmirElarbi Portals (BOI14_portals) C++14
100 / 100
 848 ms 57416 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define fi first
#define se second
#define INF 1e7
#define unsigned u
#define eps 1e-18
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);
#define MAX_A 100005
#define V 450
#define re register
#define maxi(a,b) ((a) > (b) ? (a) : (b))
ll MOD = 998244353;
using namespace std;
char grid[1005][1005];
int mov[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
int main(){
    optimise;
    int r,c;
    cin >> r >> c;
    ii start, end;
    ll dis[r][c];
    set<int> wallsc[r], wallsr[c];
    for (int i = 0; i < c; ++i)
    {
        wallsr[i].insert(-1);
        wallsr[i].insert(r);
    }
    for (int i = 0; i < r; ++i)
    {
        wallsc[i].insert(-1);
        wallsc[i].insert(c);
    }
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> grid[i][j];
            dis[i][j] = INF;
            if(grid[i][j] == 'S'){
                start.fi = i,start.se = j;
            } else if(grid[i][j] == 'C'){
                end.fi = i,end.se = j;
            } else if(grid[i][j] == '#'){
                wallsc[i].insert(j);
                wallsr[j].insert(i);
            }
        }
    }
    dis[start.fi][start.se] = 0;
    queue<ii> q;
    q.push(start);
    while(!q.empty()){
        ii cur = q.front(); q.pop();
        bool ses = false;
        auto ux = wallsr[cur.se].upper_bound(cur.fi),uy = wallsc[cur.fi].upper_bound(cur.se),lx = wallsr[cur.se].lower_bound(cur.fi), ly = wallsc[cur.fi].lower_bound(cur.se);
        lx--;ly--;
        for (int i = 0; i < 4; ++i)
        {
            int nx =  cur.fi +  mov[i][0], ny = cur.se + mov[i][1];
            if(nx < 0 || ny < 0 || nx >= r || ny >= c || grid[nx][ny] == '#') {
                ses = true;
                continue;
            }
            if(dis[nx][ny] > dis[cur.fi][cur.se] +1 ){
                dis[nx][ny] = dis[cur.fi][cur.se] +1 ;
                q.push({nx,ny});
            }
        }
        int near = min(cur.fi-*lx, cur.se-*ly);
        near = min(near, *uy-cur.se);
        near = min(near, *ux-cur.fi);
        int nx =  *ux-1, ny = cur.se;
        if(nx < 0 || ny < 0 || nx >= r || ny >= c || grid[nx][ny] == '#') 
            continue;
        if(dis[nx][ny] > dis[cur.fi][cur.se] +near ){
            dis[nx][ny] = dis[cur.fi][cur.se] +near ;
            q.push({nx,ny});
        }
        nx =  *lx+1, ny = cur.se;
        if(nx < 0 || ny < 0 || nx >= r || ny >= c || grid[nx][ny] == '#') 
            continue;
        if(dis[nx][ny] > dis[cur.fi][cur.se] +near ){
            dis[nx][ny] = dis[cur.fi][cur.se] +near ;
            q.push({nx,ny});
        }
        nx = cur.fi, ny = *ly+1;
        if(nx < 0 || ny < 0 || nx >= r || ny >= c || grid[nx][ny] == '#') 
            continue;
        if(dis[nx][ny] > dis[cur.fi][cur.se] +near ){
            dis[nx][ny] = dis[cur.fi][cur.se] +near ;
            q.push({nx,ny});
        }
        nx = cur.fi, ny = *uy-1;
        if(nx < 0 || ny < 0 || nx >= r || ny >= c || grid[nx][ny] == '#') 
            continue;
        if(dis[nx][ny] > dis[cur.fi][cur.se] +near ){
            dis[nx][ny] = dis[cur.fi][cur.se] +near ;
            q.push({nx,ny});
        }
    }
    cout << dis[end.fi][end.se];
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:65:14: warning: variable 'ses' set but not used [-Wunused-but-set-variable]
   65 |         bool ses = false;
      |              ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 204 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 13 ms 2480 KB Output is correct
6 Correct 17 ms 2388 KB Output is correct
7 Correct 14 ms 2124 KB Output is correct
8 Correct 10 ms 2168 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 452 KB Output is correct
14 Correct 14 ms 2520 KB Output is correct
15 Correct 15 ms 2380 KB Output is correct
16 Correct 18 ms 2188 KB Output is correct
17 Correct 14 ms 2220 KB Output is correct
18 Correct 17 ms 1712 KB Output is correct
19 Correct 6 ms 844 KB Output is correct
20 Correct 7 ms 960 KB Output is correct
21 Correct 14 ms 2380 KB Output is correct
22 Correct 14 ms 2380 KB Output is correct
23 Correct 15 ms 2252 KB Output is correct
24 Correct 4 ms 844 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 0 ms 204 KB Output is correct
28 Correct 10 ms 2128 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 16 ms 2520 KB Output is correct
15 Correct 14 ms 2380 KB Output is correct
16 Correct 16 ms 2124 KB Output is correct
17 Correct 13 ms 2252 KB Output is correct
18 Correct 14 ms 1768 KB Output is correct
19 Correct 8 ms 844 KB Output is correct
20 Correct 8 ms 948 KB Output is correct
21 Correct 18 ms 2380 KB Output is correct
22 Correct 19 ms 2412 KB Output is correct
23 Correct 14 ms 2252 KB Output is correct
24 Correct 848 ms 39532 KB Output is correct
25 Correct 178 ms 9796 KB Output is correct
26 Correct 162 ms 10412 KB Output is correct
27 Correct 210 ms 10496 KB Output is correct
28 Correct 611 ms 50628 KB Output is correct
29 Correct 623 ms 49152 KB Output is correct
30 Correct 690 ms 48208 KB Output is correct
31 Correct 4 ms 844 KB Output is correct
32 Correct 109 ms 10464 KB Output is correct
33 Correct 0 ms 332 KB Output is correct
34 Correct 1 ms 460 KB Output is correct
35 Correct 353 ms 33944 KB Output is correct
36 Correct 1 ms 328 KB Output is correct
37 Correct 10 ms 2124 KB Output is correct
38 Correct 348 ms 41624 KB Output is correct
39 Correct 368 ms 57416 KB Output is correct