답안 #49732 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49732	2018-06-02T10:59:45 Z	imeimi2000	Dangerous Skating (JOI16_skating)	C++17	100 / 100	529 ms	22160 KB

skating

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

struct node {
    int x, y, d;
    bool operator<(const node &p) const {
        return d > p.d;
    }
};

const int inf = 1e8;
int r, c;
char grid[1000][1001];
int close[4][1000][1000];
int dist[1000][1000];
priority_queue<node> pq;
void pushDist(int x, int y, int d) {
    if (0 <= x && x < r && 0 <= y && y < c) {
        if (grid[x][y] == '#') return;
        if (dist[x][y] <= d) return;
        dist[x][y] = d;
        pq.push({ x, y, d });
    }
}
const int gox[4] = { -1, 0, 1, 0 };
const int goy[4] = { 0, -1, 0, 1 };
int main() {
	scanf("%d%d", &r, &c);
	int sx, sy, ex, ey;
	for (int i = 0; i < r; ++i) {
        scanf("%s", grid[i]);
        for (int j = 0; j < c; ++j) {
            dist[i][j] = inf;
        }
	}
	scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
	--sx; --sy;
	--ex; --ey;
	for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (grid[i][j] != '#') {
                close[0][i][j] = close[0][i - 1][j] + 1;
                close[1][i][j] = close[1][i][j - 1] + 1;
            }
            else close[0][i][j] = close[1][i][j] = -1;
        }
	}
	for (int i = r; i--; ) {
        for (int j = c; j--; ) {
            if (grid[i][j] != '#') {
                close[2][i][j] = close[2][i + 1][j] + 1;
                close[3][i][j] = close[3][i][j + 1] + 1;
            }
            else close[2][i][j] = close[3][i][j] = -1;
        }
	}
	pushDist(sx, sy, 0);
	while (!pq.empty()) {
        node tp = pq.top();
        pq.pop();
        int x = tp.x, y = tp.y, d = tp.d;
        if (x == ex && y == ey) {
            printf("%d\n", d);
            return 0;
        }
        if (dist[x][y] != d) continue;
        for (int i = 0; i < 4; ++i) {
            int l = close[i][x][y];
            pushDist(x + gox[i] * l, y + goy[i] * l, d + 1);
            pushDist(x + gox[i], y + goy[i], d + 2);
        }
	}
	printf("-1\n");
	return 0;
}

Compilation message

skating.cpp: In function 'int main()':
skating.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &r, &c);
  ~~~~~^~~~~~~~~~~~~~~~
skating.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", grid[i]);
         ~~~~~^~~~~~~~~~~~~~~
skating.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct
3	Correct	3 ms	616 KB	Output is correct
4	Correct	3 ms	672 KB	Output is correct
5	Correct	2 ms	672 KB	Output is correct
6	Correct	3 ms	748 KB	Output is correct
7	Correct	4 ms	800 KB	Output is correct
8	Correct	2 ms	800 KB	Output is correct
9	Correct	3 ms	800 KB	Output is correct
10	Correct	3 ms	800 KB	Output is correct

Subtask #2
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct
3	Correct	3 ms	616 KB	Output is correct
4	Correct	3 ms	672 KB	Output is correct
5	Correct	2 ms	672 KB	Output is correct
6	Correct	3 ms	748 KB	Output is correct
7	Correct	4 ms	800 KB	Output is correct
8	Correct	2 ms	800 KB	Output is correct
9	Correct	3 ms	800 KB	Output is correct
10	Correct	3 ms	800 KB	Output is correct
11	Correct	10 ms	4664 KB	Output is correct
12	Correct	12 ms	4664 KB	Output is correct
13	Correct	10 ms	4792 KB	Output is correct
14	Correct	9 ms	4792 KB	Output is correct
15	Correct	6 ms	4792 KB	Output is correct
16	Correct	13 ms	4940 KB	Output is correct
17	Correct	11 ms	4940 KB	Output is correct
18	Correct	9 ms	4940 KB	Output is correct
19	Correct	12 ms	4940 KB	Output is correct
20	Correct	9 ms	4940 KB	Output is correct
21	Correct	9 ms	4940 KB	Output is correct
22	Correct	30 ms	4940 KB	Output is correct
23	Correct	12 ms	4940 KB	Output is correct
24	Correct	20 ms	4940 KB	Output is correct
25	Correct	9 ms	4940 KB	Output is correct
26	Correct	10 ms	4940 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct
3	Correct	3 ms	616 KB	Output is correct
4	Correct	3 ms	672 KB	Output is correct
5	Correct	2 ms	672 KB	Output is correct
6	Correct	3 ms	748 KB	Output is correct
7	Correct	4 ms	800 KB	Output is correct
8	Correct	2 ms	800 KB	Output is correct
9	Correct	3 ms	800 KB	Output is correct
10	Correct	3 ms	800 KB	Output is correct
11	Correct	10 ms	4664 KB	Output is correct
12	Correct	12 ms	4664 KB	Output is correct
13	Correct	10 ms	4792 KB	Output is correct
14	Correct	9 ms	4792 KB	Output is correct
15	Correct	6 ms	4792 KB	Output is correct
16	Correct	13 ms	4940 KB	Output is correct
17	Correct	11 ms	4940 KB	Output is correct
18	Correct	9 ms	4940 KB	Output is correct
19	Correct	12 ms	4940 KB	Output is correct
20	Correct	9 ms	4940 KB	Output is correct
21	Correct	9 ms	4940 KB	Output is correct
22	Correct	30 ms	4940 KB	Output is correct
23	Correct	12 ms	4940 KB	Output is correct
24	Correct	20 ms	4940 KB	Output is correct
25	Correct	9 ms	4940 KB	Output is correct
26	Correct	10 ms	4940 KB	Output is correct
27	Correct	287 ms	21436 KB	Output is correct
28	Correct	529 ms	22008 KB	Output is correct
29	Correct	32 ms	22008 KB	Output is correct
30	Correct	123 ms	22008 KB	Output is correct
31	Correct	34 ms	22008 KB	Output is correct
32	Correct	235 ms	22008 KB	Output is correct
33	Correct	36 ms	22008 KB	Output is correct
34	Correct	90 ms	22008 KB	Output is correct
35	Correct	220 ms	22008 KB	Output is correct
36	Correct	148 ms	22008 KB	Output is correct
37	Correct	99 ms	22008 KB	Output is correct
38	Correct	502 ms	22160 KB	Output is correct
39	Correct	244 ms	22160 KB	Output is correct
40	Correct	52 ms	22160 KB	Output is correct

답안 #49732

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