oj.uz

답안 #699865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699865 2023-02-18T07:27:56 Z happypotato Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 87300 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxN = 3e4 + 1;
pair<int, int> doge[mxN];
queue<int> jump[mxN];
map<int, int> dist[mxN];
queue<pair<int, int>> q[2];
int curdist = 0;
bool flag = false;
int n;
void PushElement(pair<int, pair<int, int>> &nxt) {
	q[flag ^ (nxt.first != curdist)].push(nxt.second);
}
void AddElement(pair<int, pair<int, int>> &nxt) {
	if (!(0 <= nxt.second.first && nxt.second.first < n)) return;
	if (dist[nxt.second.first].find(nxt.second.second) == dist[nxt.second.first].end()) {
		PushElement(nxt);
		dist[nxt.second.first][nxt.second.second] = nxt.first;
	} else if (dist[nxt.second.first][nxt.second.second] > nxt.first) {
		PushElement(nxt);
		dist[nxt.second.first][nxt.second.second] = nxt.first;
	}
}
void solve() {
	int m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> doge[i].first >> doge[i].second;
		if (i != 0) jump[doge[i].first].push(doge[i].second);
	}
	pair<int, pair<int, int>> nxt;
	nxt = {0, doge[0]};
	AddElement(nxt);
	while (!q[flag].empty()) {
		while (!q[flag].empty()) {
			pair<int, int> cur = q[flag].front();
			q[flag].pop();
			if (dist[cur.first][cur.second] < curdist) continue;
			if (cur.first == doge[1].first) {
				cout << curdist << endl;
				return;
			}
			while (!jump[cur.first].empty()) {
				int delta = jump[cur.first].front();
				jump[cur.first].pop();
				nxt = {curdist, {cur.first, delta}};
				AddElement(nxt);
			}
			nxt = {curdist + 1, {cur.first - cur.second, cur.second}};
			AddElement(nxt);
			nxt = {curdist + 1, {cur.first + cur.second, cur.second}};
			AddElement(nxt);
		}
		curdist++;
		flag ^= 1;
	}
	cout << "-1\n";
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 21844 KB Output is correct
2 Correct 14 ms 21804 KB Output is correct
3 Correct 14 ms 21844 KB Output is correct
4 Correct 14 ms 21912 KB Output is correct
5 Correct 14 ms 21928 KB Output is correct
6 Correct 14 ms 21848 KB Output is correct
7 Correct 16 ms 21912 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 21844 KB Output is correct
2 Correct 18 ms 21928 KB Output is correct
3 Correct 16 ms 21908 KB Output is correct
4 Correct 14 ms 21844 KB Output is correct
5 Correct 15 ms 21844 KB Output is correct
6 Correct 14 ms 21932 KB Output is correct
7 Correct 14 ms 21932 KB Output is correct
8 Correct 14 ms 21924 KB Output is correct
9 Correct 14 ms 21844 KB Output is correct
10 Correct 14 ms 21924 KB Output is correct
11 Correct 14 ms 21936 KB Output is correct
12 Correct 14 ms 21972 KB Output is correct
13 Correct 15 ms 21940 KB Output is correct
14 Correct 17 ms 22228 KB Output is correct
15 Correct 15 ms 22144 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 21876 KB Output is correct
2 Correct 14 ms 21844 KB Output is correct
3 Correct 14 ms 21824 KB Output is correct
4 Correct 17 ms 21920 KB Output is correct
5 Correct 15 ms 21844 KB Output is correct
6 Correct 17 ms 21936 KB Output is correct
7 Correct 14 ms 21936 KB Output is correct
8 Correct 14 ms 21832 KB Output is correct
9 Correct 14 ms 21844 KB Output is correct
10 Correct 15 ms 21824 KB Output is correct
11 Correct 16 ms 21944 KB Output is correct
12 Correct 14 ms 21972 KB Output is correct
13 Correct 13 ms 21844 KB Output is correct
14 Correct 15 ms 22188 KB Output is correct
15 Correct 17 ms 22100 KB Output is correct
16 Correct 13 ms 21892 KB Output is correct
17 Correct 14 ms 22100 KB Output is correct
18 Correct 14 ms 21844 KB Output is correct
19 Correct 14 ms 21932 KB Output is correct
20 Correct 14 ms 21936 KB Output is correct
21 Correct 13 ms 21844 KB Output is correct
22 Correct 14 ms 21864 KB Output is correct
23 Correct 15 ms 22072 KB Output is correct
24 Correct 18 ms 22228 KB Output is correct
25 Correct 15 ms 21972 KB Output is correct
26 Correct 18 ms 22100 KB Output is correct
27 Correct 17 ms 22100 KB Output is correct
28 Correct 18 ms 22868 KB Output is correct
29 Correct 38 ms 24756 KB Output is correct
30 Correct 18 ms 22612 KB Output is correct
31 Correct 20 ms 23408 KB Output is correct
32 Correct 18 ms 22980 KB Output is correct
33 Correct 57 ms 27484 KB Output is correct
34 Correct 33 ms 24936 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 21844 KB Output is correct
2 Correct 14 ms 21856 KB Output is correct
3 Correct 15 ms 21804 KB Output is correct
4 Correct 13 ms 21844 KB Output is correct
5 Correct 14 ms 21888 KB Output is correct
6 Correct 14 ms 21932 KB Output is correct
7 Correct 13 ms 21832 KB Output is correct
8 Correct 14 ms 21844 KB Output is correct
9 Correct 14 ms 21844 KB Output is correct
10 Correct 17 ms 21932 KB Output is correct
11 Correct 14 ms 21972 KB Output is correct
12 Correct 17 ms 21960 KB Output is correct
13 Correct 14 ms 21892 KB Output is correct
14 Correct 15 ms 22228 KB Output is correct
15 Correct 15 ms 22056 KB Output is correct
16 Correct 14 ms 21848 KB Output is correct
17 Correct 14 ms 22100 KB Output is correct
18 Correct 14 ms 21888 KB Output is correct
19 Correct 14 ms 21940 KB Output is correct
20 Correct 14 ms 22032 KB Output is correct
21 Correct 14 ms 21940 KB Output is correct
22 Correct 13 ms 21920 KB Output is correct
23 Correct 14 ms 22072 KB Output is correct
24 Correct 16 ms 22228 KB Output is correct
25 Correct 13 ms 21972 KB Output is correct
26 Correct 14 ms 22068 KB Output is correct
27 Correct 16 ms 22104 KB Output is correct
28 Correct 18 ms 22776 KB Output is correct
29 Correct 29 ms 24772 KB Output is correct
30 Correct 17 ms 22704 KB Output is correct
31 Correct 25 ms 23448 KB Output is correct
32 Correct 18 ms 22996 KB Output is correct
33 Correct 57 ms 27496 KB Output is correct
34 Correct 32 ms 24932 KB Output is correct
35 Correct 27 ms 24160 KB Output is correct
36 Correct 19 ms 22068 KB Output is correct
37 Correct 20 ms 23004 KB Output is correct
38 Correct 24 ms 23856 KB Output is correct
39 Correct 19 ms 22224 KB Output is correct
40 Correct 19 ms 22228 KB Output is correct
41 Correct 20 ms 22820 KB Output is correct
42 Correct 18 ms 22484 KB Output is correct
43 Correct 20 ms 22564 KB Output is correct
44 Correct 18 ms 22456 KB Output is correct
45 Correct 289 ms 44732 KB Output is correct
46 Correct 135 ms 35068 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 21844 KB Output is correct
2 Correct 13 ms 21904 KB Output is correct
3 Correct 14 ms 21856 KB Output is correct
4 Correct 14 ms 21932 KB Output is correct
5 Correct 14 ms 21904 KB Output is correct
6 Correct 13 ms 21900 KB Output is correct
7 Correct 13 ms 21928 KB Output is correct
8 Correct 13 ms 21848 KB Output is correct
9 Correct 14 ms 21844 KB Output is correct
10 Correct 13 ms 21932 KB Output is correct
11 Correct 14 ms 21844 KB Output is correct
12 Correct 15 ms 21972 KB Output is correct
13 Correct 14 ms 21940 KB Output is correct
14 Correct 15 ms 22188 KB Output is correct
15 Correct 17 ms 22124 KB Output is correct
16 Correct 14 ms 21908 KB Output is correct
17 Correct 15 ms 22084 KB Output is correct
18 Correct 14 ms 21844 KB Output is correct
19 Correct 13 ms 21844 KB Output is correct
20 Correct 15 ms 21940 KB Output is correct
21 Correct 14 ms 21956 KB Output is correct
22 Correct 15 ms 21860 KB Output is correct
23 Correct 15 ms 22060 KB Output is correct
24 Correct 16 ms 22200 KB Output is correct
25 Correct 15 ms 21956 KB Output is correct
26 Correct 14 ms 22076 KB Output is correct
27 Correct 17 ms 22100 KB Output is correct
28 Correct 20 ms 22848 KB Output is correct
29 Correct 30 ms 24748 KB Output is correct
30 Correct 18 ms 22660 KB Output is correct
31 Correct 24 ms 23364 KB Output is correct
32 Correct 18 ms 22996 KB Output is correct
33 Correct 54 ms 27496 KB Output is correct
34 Correct 35 ms 24888 KB Output is correct
35 Correct 28 ms 24140 KB Output is correct
36 Correct 15 ms 22032 KB Output is correct
37 Correct 20 ms 23012 KB Output is correct
38 Correct 25 ms 23916 KB Output is correct
39 Correct 18 ms 22228 KB Output is correct
40 Correct 19 ms 22232 KB Output is correct
41 Correct 20 ms 22852 KB Output is correct
42 Correct 18 ms 22540 KB Output is correct
43 Correct 20 ms 22564 KB Output is correct
44 Correct 18 ms 22452 KB Output is correct
45 Correct 307 ms 44764 KB Output is correct
46 Correct 141 ms 35020 KB Output is correct
47 Correct 23 ms 23140 KB Output is correct
48 Correct 20 ms 22224 KB Output is correct
49 Correct 20 ms 22100 KB Output is correct
50 Correct 19 ms 22100 KB Output is correct
51 Correct 36 ms 24584 KB Output is correct
52 Correct 43 ms 25096 KB Output is correct
53 Correct 24 ms 22612 KB Output is correct
54 Correct 16 ms 22572 KB Output is correct
55 Correct 16 ms 23056 KB Output is correct
56 Correct 25 ms 23584 KB Output is correct
57 Correct 14 ms 21968 KB Output is correct
58 Correct 25 ms 25428 KB Output is correct
59 Correct 25 ms 25012 KB Output is correct
60 Correct 28 ms 25044 KB Output is correct
61 Correct 27 ms 24836 KB Output is correct
62 Correct 228 ms 43236 KB Output is correct
63 Execution timed out 1088 ms 87300 KB Time limit exceeded
64 Halted 0 ms 0 KB -