답안 #519717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519717	2022-01-27T06:54:56 Z	naal	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	22 ms	39884 KB

skyscraper

// https://oj.uz/problem/view/APIO15_skyscraper
#include <bits/stdc++.h>
using namespace std;

#define Fname ((string) "io")
#define int long long
#define ii pair <int, int>
#define iii pair <int, ii>
#define fi first
#define se second
#define endl '\n'
const int INF = 1e16;
const int N = 3e3 + 5;

int n, m, d[N][N], goal;
vector <int> a[N];
priority_queue <iii, vector <iii>, greater <iii>> pq;

int find(int u) {
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= n; j++)
			d[i][j] = INF;
	pq.push({0, {u, 0}});
	d[u][0] = 0;
	while (pq.size()) {
		u = pq.top().se.fi;
		int step = pq.top().se.se, total = pq.top().fi;
		pq.pop();
		if (total != d[u][step])
			continue;
		if (u == goal)
			return total;
		a[u].push_back(step);
		for (int &step : a[u]) {
			d[u][step] = min(d[u][step], total);
			if (u + step <= n && d[u + step][step] > d[u][step] + 1) {
				d[u + step][step] = d[u][step] + 1;
				pq.push({d[u][step] + 1, {u + step, step}});
			}
			if (u - step > 0 && d[u - step][step] > d[u][step] + 1) {
				d[u - step][step] = d[u][step] + 1;
				pq.push({d[u][step] + 1, {u - step, step}});
			}		
		}
		a[u].pop_back();
	}
	return -1;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifdef lan_ngu
		freopen((Fname + ".inp").c_str(), "r", stdin);
		freopen((Fname + ".out").c_str(), "w", stdout);
	#endif

	// int _nt; cin >> _nt;
	int _nt = 1;
	while (_nt--) {
		cin >> n >> m;
		int init;
		for (int i = 1; i <= m; i++) {
			int b, p; cin >> b >> p;
			a[b].push_back(p);
			if (i == 1)
				init = b;
			else if (i == 2)
				goal = b;
		}	
		cout << find(init);
	}

	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:71:20: warning: 'init' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |   cout << find(init);
      |                    ^

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	0 ms	460 KB	Output is correct
9	Correct	0 ms	588 KB	Output is correct
10	Correct	1 ms	844 KB	Output is correct
11	Correct	1 ms	844 KB	Output is correct
12	Correct	1 ms	844 KB	Output is correct
13	Correct	1 ms	844 KB	Output is correct
14	Correct	2 ms	972 KB	Output is correct
15	Correct	2 ms	972 KB	Output is correct

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	460 KB	Output is correct
9	Correct	1 ms	588 KB	Output is correct
10	Correct	1 ms	844 KB	Output is correct
11	Correct	1 ms	844 KB	Output is correct
12	Correct	1 ms	844 KB	Output is correct
13	Correct	1 ms	844 KB	Output is correct
14	Correct	2 ms	1004 KB	Output is correct
15	Correct	1 ms	972 KB	Output is correct
16	Correct	2 ms	1484 KB	Output is correct
17	Correct	4 ms	7756 KB	Output is correct
18	Correct	14 ms	31232 KB	Output is correct
19	Correct	19 ms	39656 KB	Output is correct
20	Correct	19 ms	39756 KB	Output is correct
21	Correct	2 ms	3148 KB	Output is correct
22	Correct	14 ms	32336 KB	Output is correct
23	Correct	14 ms	27016 KB	Output is correct
24	Correct	19 ms	36428 KB	Output is correct
25	Correct	19 ms	39756 KB	Output is correct
26	Correct	18 ms	39756 KB	Output is correct
27	Correct	18 ms	39740 KB	Output is correct
28	Incorrect	22 ms	39884 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	0 ms	460 KB	Output is correct
9	Correct	0 ms	588 KB	Output is correct
10	Correct	1 ms	844 KB	Output is correct
11	Correct	1 ms	844 KB	Output is correct
12	Correct	1 ms	844 KB	Output is correct
13	Correct	1 ms	844 KB	Output is correct
14	Correct	2 ms	972 KB	Output is correct
15	Correct	2 ms	972 KB	Output is correct
16	Correct	1 ms	1484 KB	Output is correct
17	Correct	4 ms	7756 KB	Output is correct
18	Correct	14 ms	31308 KB	Output is correct
19	Correct	17 ms	39628 KB	Output is correct
20	Correct	18 ms	39756 KB	Output is correct
21	Correct	2 ms	3148 KB	Output is correct
22	Correct	14 ms	32332 KB	Output is correct
23	Correct	14 ms	27020 KB	Output is correct
24	Correct	18 ms	36436 KB	Output is correct
25	Correct	19 ms	39756 KB	Output is correct
26	Correct	19 ms	39756 KB	Output is correct
27	Correct	19 ms	39840 KB	Output is correct
28	Incorrect	20 ms	39672 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	1 ms	460 KB	Output is correct
9	Correct	1 ms	588 KB	Output is correct
10	Correct	1 ms	844 KB	Output is correct
11	Correct	1 ms	844 KB	Output is correct
12	Correct	1 ms	844 KB	Output is correct
13	Correct	1 ms	844 KB	Output is correct
14	Correct	2 ms	972 KB	Output is correct
15	Correct	1 ms	972 KB	Output is correct
16	Correct	1 ms	1484 KB	Output is correct
17	Correct	5 ms	7756 KB	Output is correct
18	Correct	18 ms	31300 KB	Output is correct
19	Correct	18 ms	39736 KB	Output is correct
20	Correct	18 ms	39712 KB	Output is correct
21	Correct	2 ms	3148 KB	Output is correct
22	Correct	14 ms	32312 KB	Output is correct
23	Correct	13 ms	27132 KB	Output is correct
24	Correct	19 ms	36428 KB	Output is correct
25	Correct	18 ms	39740 KB	Output is correct
26	Correct	21 ms	39764 KB	Output is correct
27	Correct	18 ms	39768 KB	Output is correct
28	Incorrect	20 ms	39756 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #519717

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 14.0

Subtask #4 0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 14.0

Subtask #4
0 / 21.0

Subtask #5
0 / 43.0