oj.uz

Submission #98034

# Submission time Handle Problem Language Result Execution time Memory
98034 2019-02-20T01:26:24 Z dndhk None (JOI16_skating) C++14
100 / 100
 691 ms 39584 KB 
#include <bits/stdc++.h>

#define push_back pb
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define F first
#define S second
#define INF 2000000000

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 1000;

int N, M;
pii st, ed;
string str[MAX_N+1];
pii L[MAX_N+1][MAX_N+1], U[MAX_N+1][MAX_N+1], D[MAX_N+1][MAX_N+1], R[MAX_N+1][MAX_N+1];

priority_queue<pair<int, pii> > pq;
int dist[MAX_N+1][MAX_N+1];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

void check(int x1, int y1, int x2, int y2){
	if(dist[x2][y2] > dist[x1][y1]+1){
		dist[x2][y2] = dist[x1][y1] + 1;
		pq.push({-dist[x2][y2], {x2, y2}});
	}
}

int main(){
	cin>>N>>M;
	for(int i=0; i<N; i++){
		cin>>str[i];
		for(int j=0; j<M; j++){
			dist[i][j] = INF;
		}
	}
	cin>>st.F>>st.S>>ed.F>>ed.S;
	st.F--; st.S--; ed.F--; ed.S--;
	for(int i=0; i<N; i++){
		pii prv;
		for(int j=0; j<M; j++){
			if(str[i][j]=='#')	prv = {i, j+1};
			else	L[i][j] = prv;
		}
		for(int j=M-1; j>=0; j--){
			if(str[i][j]=='#')	prv = {i, j-1};
			else	R[i][j] = prv;
		}
	}
	for(int j=0; j<M; j++){
		pii prv;
		for(int i=0; i<N; i++){
			if(str[i][j]=='#')	prv = {i+1, j};
			else	U[i][j] = prv;
		}
		for(int i=N-1; i>=0; i--){
			if(str[i][j]=='#')	prv = {i-1, j};
			else	D[i][j] = prv;
		}
	}
	dist[st.F][st.S] = 0;
	pq.push({0, st});
	while(!pq.empty()){
		pair<int, pii> now = pq.top(); pq.pop();
		now.F = -now.F;
		if(dist[now.S.F][now.S.S]!=now.F)	continue;
		pii idx = now.S;
		//cout<<now.F<<' '<<idx.F<<' '<<idx.S<<endl;
		if(idx==ed)	break;
		for(int k=0; k<4; k++){
			if(idx.F+dx[k]<0 || idx.F+dx[k]>=N || idx.S+dy[k]<0 || idx.S+dy[k]>=M)	continue;
			if(str[idx.F+dx[k]][idx.S+dy[k]]=='#') continue;
			if(dist[idx.F+dx[k]][idx.S+dy[k]] > dist[idx.F][idx.S] + 2){
				dist[idx.F+dx[k]][idx.S+dy[k]] = dist[idx.F][idx.S]+2;
				pq.push({-dist[idx.F+dx[k]][idx.S+dy[k]], {idx.F+dx[k], idx.S+dy[k]}});
			}
		}
		check(idx.F, idx.S, L[idx.F][idx.S].F, L[idx.F][idx.S].S);
		check(idx.F, idx.S, R[idx.F][idx.S].F, R[idx.F][idx.S].S);
		check(idx.F, idx.S, D[idx.F][idx.S].F, D[idx.F][idx.S].S);
		check(idx.F, idx.S, U[idx.F][idx.S].F, U[idx.F][idx.S].S);
	}
	if(dist[ed.F][ed.S]==INF)	printf("-1");
	else	printf("%d", dist[ed.F][ed.S]);
	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 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 3 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
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 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 3 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 13 ms 5760 KB Output is correct
12 Correct 16 ms 5744 KB Output is correct
13 Correct 12 ms 5836 KB Output is correct
14 Correct 12 ms 5632 KB Output is correct
15 Correct 9 ms 5632 KB Output is correct
16 Correct 18 ms 5840 KB Output is correct
17 Correct 20 ms 5632 KB Output is correct
18 Correct 13 ms 5632 KB Output is correct
19 Correct 17 ms 5760 KB Output is correct
20 Correct 10 ms 5376 KB Output is correct
21 Correct 13 ms 5672 KB Output is correct
22 Correct 11 ms 4864 KB Output is correct
23 Correct 16 ms 5760 KB Output is correct
24 Correct 19 ms 5700 KB Output is correct
25 Correct 12 ms 5632 KB Output is correct
26 Correct 16 ms 5632 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 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 3 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 13 ms 5760 KB Output is correct
12 Correct 16 ms 5744 KB Output is correct
13 Correct 12 ms 5836 KB Output is correct
14 Correct 12 ms 5632 KB Output is correct
15 Correct 9 ms 5632 KB Output is correct
16 Correct 18 ms 5840 KB Output is correct
17 Correct 20 ms 5632 KB Output is correct
18 Correct 13 ms 5632 KB Output is correct
19 Correct 17 ms 5760 KB Output is correct
20 Correct 10 ms 5376 KB Output is correct
21 Correct 13 ms 5672 KB Output is correct
22 Correct 11 ms 4864 KB Output is correct
23 Correct 16 ms 5760 KB Output is correct
24 Correct 19 ms 5700 KB Output is correct
25 Correct 12 ms 5632 KB Output is correct
26 Correct 16 ms 5632 KB Output is correct
27 Correct 390 ms 38768 KB Output is correct
28 Correct 691 ms 39584 KB Output is correct
29 Correct 105 ms 39004 KB Output is correct
30 Correct 272 ms 39016 KB Output is correct
31 Correct 103 ms 38424 KB Output is correct
32 Correct 384 ms 38632 KB Output is correct
33 Correct 57 ms 18680 KB Output is correct
34 Correct 163 ms 38520 KB Output is correct
35 Correct 369 ms 38832 KB Output is correct
36 Correct 326 ms 38764 KB Output is correct
37 Correct 152 ms 38392 KB Output is correct
38 Correct 577 ms 39344 KB Output is correct
39 Correct 229 ms 38600 KB Output is correct
40 Correct 86 ms 32120 KB Output is correct