답안 #98034 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98034	2019-02-20T01:26:24 Z	dndhk	Dangerous Skating (JOI16_skating)	C++14	100 / 100	691 ms	39584 KB

skating

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #98034

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 65.0 / 65.0

Subtask #3 22.0 / 22.0

Subtask #1
13.0 / 13.0

Subtask #2
65.0 / 65.0

Subtask #3
22.0 / 22.0