oj.uz

답안 #257333

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257333 2020-08-04T06:21:21 Z 임성재(#5052) Dangerous Skating (JOI16_skating) C++17
13 / 100
 8 ms 2684 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,pii> pipii;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
string s[1010];
priority_queue<pipii, vector<pipii>, greater<pipii>> pQ;
pii S;
pii E;
bool chk[1010][1010];
bool chk1[1010][1010];
bool chk2[1010][1010];
int dis[1010][1010];

int main() {
	fast;

	cin >> n >> m;

	for(int i=0; i<n; i++) {
		cin >> s[i];
	}

	cin >> S.fi >> S.se;
	cin >> E.fi >> E.se;

	S.fi--;
	S.se--;
	E.fi--;
	E.se--;

	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			dis[i][j] = inf;
		}
	}

	pQ.em(0, S);

	while(pQ.size()) {
		int cost = pQ.top().fi;
		pii cur = pQ.top().se;

		pQ.pop();

		if(cur == E) {
			cout << cost << "\n";
			return 0;
		}
		if(chk[cur.fi][cur.se]) continue;
		chk[cur.fi][cur.se] = true;
		
		if(!chk1[cur.fi][cur.se]) {
			int l, r;
			for(l = cur.fi; 0 <= l && s[l][cur.se] == '.'; l--);
			for(r = cur.fi; r < n && s[r][cur.se] == '.'; r++);

			l++;
			r--;

			for(int i=l; i<=r; i++) {
				chk1[i][cur.se] = true;
				
				if(i < cur.fi) {
					int d = min(2 * i - 2 * l + 1, 2 * cur.fi - 2 * i);

					if(cost + d >= dis[i][cur.se]) continue;
					dis[i][cur.se] = cost + d;
					pQ.em(cost + d, mp(i, cur.se));
				}
				else if(i > cur.fi) {
					int d = min(2 * r - 2 * i + 1, 2 * i - 2 * cur.fi);				
					
					if(cost + d >= dis[i][cur.se]) continue;
					dis[i][cur.se] = cost + d;
					pQ.em(cost + d, mp(i, cur.se));
				}
			}
		}

		if(!chk2[cur.fi][cur.se]) {
			int l, r;
			for(l = cur.se; 0 <= l && s[cur.fi][l] == '.'; l--);
			for(r = cur.se; r < m && s[cur.fi][r] == '.'; r++);

			l++;
			r--;

			for(int i=l; i<=r; i++) {
				chk2[cur.fi][i] = true;
				if(i < cur.se) {
					int d = min(2 * i - 2 * l + 1, 2 * cur.se - 2 * i);

					if(cost + d >= dis[cur.fi][i]) continue;
					dis[cur.fi][i] = cost + d;
					pQ.em(cost + d, mp(cur.fi, i));
				}
				else if(i > cur.se) {
					int d = min(2 * r - 2 * i + 1, 2 * i - 2 * cur.se);				
					
					if(cost + d >= dis[cur.fi][i]) continue;
					dis[cur.fi][i] = cost + d;
					pQ.em(cost + d, mp(cur.fi, i));
				}
			}
		}
	}

	cout << "-1\n";
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 416 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 416 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 7 ms 2556 KB Output is correct
12 Incorrect 8 ms 2684 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 416 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 7 ms 2556 KB Output is correct
12 Incorrect 8 ms 2684 KB Output isn't correct
13 Halted 0 ms 0 KB -