oj.uz

답안 #977520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
977520 2024-05-08T06:10:05 Z Amaarsaa Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 5 ms 1368 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
ll D[30005];
vector < ll > v[30005];
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll t, n, m, ans, s, sum,dist, x, y, r, p, i, j;
	
	cin >> m >> n;
	
	priority_queue < pair < ll, ll >, vector < pair < ll, ll >> , greater < pair < ll, ll >> > pq;
	
	ll a[n + 2], b[n + 2];
	for (i = 0; i < n; i ++) {
		cin >> a[i] >> b[i];
		v[a[i]].push_back(b[i]);
	}
	for (i = 1; i <= m; i ++) D[i] = 1e18;
	D[a[0]] = 0;
	pq.push({0, a[0]});
	while(!pq.empty()) {
		x = pq.top().first;
		y = pq.top().second;
		pq.pop();
		if ( x != D[y]) continue;
		for ( ll X : v[y]) {
			s = y - X;
			dist = 1;
			while ( s >= 0) {
				
				if ( D[s] > D[y] + dist) {
					D[s] = D[y] + dist;
					pq.push({D[s], s});
				}
				dist ++;
				s -= X;
			}
			s = y + X;
			dist = 1;
			while ( s < m) {
				if ( D[s] > D[y] + dist) {
					D[s] = D[y] + dist;
					pq.push({D[s], s});
				}
				dist ++;
				s += X;
			}
		}
	}
	if ( D[a[1]] == 1e18) cout << -1 << endl;
	else cout << D[a[1]] << endl;
	
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:12:5: warning: unused variable 't' [-Wunused-variable]
   12 |  ll t, n, m, ans, s, sum,dist, x, y, r, p, i, j;
      |     ^
skyscraper.cpp:12:14: warning: unused variable 'ans' [-Wunused-variable]
   12 |  ll t, n, m, ans, s, sum,dist, x, y, r, p, i, j;
      |              ^~~
skyscraper.cpp:12:22: warning: unused variable 'sum' [-Wunused-variable]
   12 |  ll t, n, m, ans, s, sum,dist, x, y, r, p, i, j;
      |                      ^~~
skyscraper.cpp:12:38: warning: unused variable 'r' [-Wunused-variable]
   12 |  ll t, n, m, ans, s, sum,dist, x, y, r, p, i, j;
      |                                      ^
skyscraper.cpp:12:41: warning: unused variable 'p' [-Wunused-variable]
   12 |  ll t, n, m, ans, s, sum,dist, x, y, r, p, i, j;
      |                                         ^
skyscraper.cpp:12:47: warning: unused variable 'j' [-Wunused-variable]
   12 |  ll t, n, m, ans, s, sum,dist, x, y, r, p, i, j;
      |                                               ^

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1184 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1112 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1112 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1368 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1112 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1368 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 4 ms 1340 KB Output is correct
21 Correct 1 ms 1112 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 3 ms 1116 KB Output is correct
27 Correct 3 ms 1112 KB Output is correct
28 Incorrect 1 ms 1112 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1316 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 4 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1188 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1200 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 3 ms 1116 KB Output is correct
27 Correct 3 ms 1116 KB Output is correct
28 Incorrect 1 ms 1116 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1112 KB Output is correct
13 Correct 1 ms 1112 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 5 ms 1112 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 2 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 3 ms 1116 KB Output is correct
27 Correct 3 ms 1268 KB Output is correct
28 Incorrect 1 ms 1116 KB Output isn't correct
29 Halted 0 ms 0 KB -