oj.uz

Submission #97498

# Submission time Handle Problem Language Result Execution time Memory
97498 2019-02-16T12:51:34 Z easrui None (JOI16_skating) C++14
13 / 100
 9 ms 4480 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
const int MAX = 1005;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppp;
int R,C,sx,sy,ex,ey,cnt,dis[MAX][MAX],l[MAX][MAX],r[MAX][MAX],u[MAX][MAX],d[MAX][MAX];
bool init[MAX][MAX];
char c;

queue<ppp> Q;
int main()
{
    cin >> R >> C;
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            cin >> c;
            if(c=='.') init[i][j] = 1;
            dis[i][j] = 1e6;
        }
    }
    cin >> sy >> sx >> ey >> ex;
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            if(init[i][j]) l[i][j] = cnt;
            else cnt = j;
        }
        for(int j=C; j>=1; j--){
            if(init[i][j]) r[i][j] = cnt;
            else cnt = j;
        }
    }
    for(int j=1; j<=C; j++){
        for(int i=1; i<=R; i++){
            if(init[i][j]) u[i][j] = cnt;
            else cnt = i;
        }
        for(int i=R; i>=1; i--){
            if(init[i][j]) d[i][j] = cnt;
            else cnt = i;
        }
    }
    dis[sy][sx] = 0;
    Q.push(ppp(pii(sy,sx),pii(sy,sx)));
    while(!Q.empty()){
        ppp cur = Q.front();
        int x = cur.va.vb, y = cur.va.va, vx = cur.vb.vb, vy = cur.vb.va, D = dis[y][x], val;
        Q.pop();
        val = l[y][x]+1;
        if(dis[y][val]>=D+1){
            dis[y][val] = D+1;
            Q.push(ppp(pii(y,val),pii(y,x)));
        }
        val = r[y][x]-1;
        if(dis[y][val]>=D+1){
            dis[y][val] = D+1;
            Q.push(ppp(pii(y,val),pii(y,x)));
        }
        val = u[y][x]+1;
        if(dis[val][x]>=D+1){
            dis[val][x] = D+1;
            Q.push(ppp(pii(val,x),pii(y,x)));
        }
        val = d[y][x]-1;
        if(dis[val][x]>=D+1){
            dis[val][x] = D+1;
            Q.push(ppp(pii(val,x),pii(y,x)));
        }
        if(vx==x && vy==y) continue;
        if(vx==x){
            if(vy<y){
                val = vy+1;
                if(dis[val][x]>=D+1){
                    dis[val][x] = D+1;
                    Q.push(ppp(pii(val,x),pii(y,x)));
                }
            }
            else{
                val = vy-1;
                if(dis[val][x]>=D+1){
                    dis[val][x] = D+1;
                    Q.push(ppp(pii(val,x),pii(y,x)));
                }
            }
        }
        if(vy==y){
            if(vx<x){
                val = vx+1;
                if(dis[y][val]>=D+1){
                    dis[y][val] = D+1;
                    Q.push(ppp(pii(y,val),pii(y,x)));
                }
            }
            else{
                val = vx-1;
                if(dis[y][val]>=D+1){
                    dis[y][val] = D+1;
                    Q.push(ppp(pii(y,val),pii(y,x)));
                }
            }
        }
    }
    if(dis[ey][ex]==1e6) cout << -1;
    else cout << dis[ey][ex];
}

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 9 ms 4480 KB Output is correct
12 Incorrect 9 ms 4480 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 9 ms 4480 KB Output is correct
12 Incorrect 9 ms 4480 KB Output isn't correct
13 Halted 0 ms 0 KB -