답안 #48166 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48166	2018-05-10T12:07:40 Z	E869120	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1000 ms	103440 KB

skyscraper

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
#include <cmath>
using namespace std;

int N, M, A[30009], P[30009], dist[7400009], sz; pair<int, int>vec[2400009];
vector<pair<int, int>>X[2400009]; vector<int> G[30009];
map<pair<int, int>, int>M1; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>Q;

void connect(int px, int py, int qx, int qy, int cost) {
	int pos1 = lower_bound(vec, vec + sz, make_pair(px, py)) - vec;
	int pos2 = lower_bound(vec, vec + sz, make_pair(qx, qy)) - vec;
	X[pos1].push_back(make_pair(pos2, cost));
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		cin >> A[i] >> P[i]; G[A[i]].push_back(P[i]);
		if (M1[make_pair(A[i] % P[i], P[i])] == 0) {
			M1[make_pair(A[i] % P[i], P[i])] = 1;
			for (int j = A[i] % P[i]; j < N; j += P[i]) { vec[sz] = make_pair(j, P[i]); sz++; }
		}
	}
	for (int i = 0; i < N; i++) { sort(G[i].begin(), G[i].end()); vec[sz] = make_pair(i, 0); sz++; }
	sort(vec, vec + sz);
	
	for (int i = 0; i < sz; i++) {
		int pos = vec[i].first, state = vec[i].second;

		if (state == 0) {
			int pos1 = lower_bound(vec, vec + sz, make_pair(pos, 0)) - vec;
			int cx = pos1;
			for (int j = 0; j < G[pos].size(); j++) {
				while (vec[cx] != make_pair(pos, G[pos][j])) cx++;
				X[pos1].push_back(make_pair(cx, 0));
			}
		}
		else {
			connect(pos, state, pos, 0, 0);
			if (pos - state >= 0) connect(pos, state, pos - state, state, 1);
			if (pos + state < N) connect(pos, state, pos + state, state, 1);
		}
	}
	for (int i = 0; i < sz; i++) dist[i] = (1 << 30);
	int sx = lower_bound(vec, vec + sz, make_pair(A[1], 0)) - vec;
	int gx = lower_bound(vec, vec + sz, make_pair(A[2], 0)) - vec;
	dist[sx] = 0; Q.push(make_pair(dist[sx], sx));

	while (!Q.empty()) {
		int pos = Q.top().second; Q.pop();
		
		for (int i = 0; i < X[pos].size(); i++) {
			int to = X[pos][i].first, cost = X[pos][i].second;
			if (dist[to] > dist[pos] + cost) {
				dist[to] = dist[pos] + cost;
				Q.push(make_pair(dist[to], to));
			}
		}
	}
	int ans = dist[gx]; if (ans == (1 << 30)) ans = -1;
	cout << ans << endl;
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[pos].size(); j++) {
                    ~~^~~~~~~~~~~~~~~
skyscraper.cpp:57:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < X[pos].size(); i++) {
                   ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	57336 KB	Output is correct
2	Correct	47 ms	57444 KB	Output is correct
3	Correct	48 ms	57520 KB	Output is correct
4	Correct	47 ms	57520 KB	Output is correct
5	Correct	49 ms	57596 KB	Output is correct
6	Correct	49 ms	57672 KB	Output is correct
7	Correct	49 ms	57708 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	48 ms	57724 KB	Output is correct
2	Correct	49 ms	57724 KB	Output is correct
3	Correct	49 ms	57724 KB	Output is correct
4	Correct	50 ms	57724 KB	Output is correct
5	Correct	50 ms	57724 KB	Output is correct
6	Correct	51 ms	57724 KB	Output is correct
7	Correct	51 ms	57724 KB	Output is correct
8	Correct	48 ms	57724 KB	Output is correct
9	Correct	47 ms	57724 KB	Output is correct
10	Correct	49 ms	57724 KB	Output is correct
11	Correct	52 ms	58108 KB	Output is correct
12	Correct	49 ms	58108 KB	Output is correct
13	Correct	48 ms	58108 KB	Output is correct
14	Correct	53 ms	58108 KB	Output is correct
15	Correct	53 ms	58108 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	58108 KB	Output is correct
2	Correct	48 ms	58108 KB	Output is correct
3	Correct	48 ms	58108 KB	Output is correct
4	Correct	48 ms	58108 KB	Output is correct
5	Correct	51 ms	58108 KB	Output is correct
6	Correct	48 ms	58108 KB	Output is correct
7	Correct	47 ms	58108 KB	Output is correct
8	Correct	45 ms	58108 KB	Output is correct
9	Correct	48 ms	58108 KB	Output is correct
10	Correct	49 ms	58108 KB	Output is correct
11	Correct	52 ms	58108 KB	Output is correct
12	Correct	51 ms	58108 KB	Output is correct
13	Correct	48 ms	58108 KB	Output is correct
14	Correct	55 ms	58108 KB	Output is correct
15	Correct	53 ms	58108 KB	Output is correct
16	Correct	50 ms	58108 KB	Output is correct
17	Correct	62 ms	58624 KB	Output is correct
18	Correct	54 ms	58624 KB	Output is correct
19	Correct	51 ms	58624 KB	Output is correct
20	Correct	51 ms	58624 KB	Output is correct
21	Correct	49 ms	58624 KB	Output is correct
22	Correct	52 ms	58624 KB	Output is correct
23	Correct	54 ms	58624 KB	Output is correct
24	Correct	62 ms	58624 KB	Output is correct
25	Correct	56 ms	58624 KB	Output is correct
26	Correct	55 ms	58624 KB	Output is correct
27	Correct	54 ms	58624 KB	Output is correct
28	Correct	69 ms	59260 KB	Output is correct
29	Correct	103 ms	61436 KB	Output is correct
30	Correct	62 ms	61436 KB	Output is correct
31	Correct	80 ms	61436 KB	Output is correct
32	Correct	70 ms	61436 KB	Output is correct
33	Correct	166 ms	64884 KB	Output is correct
34	Correct	163 ms	64892 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	52 ms	64892 KB	Output is correct
2	Correct	50 ms	64892 KB	Output is correct
3	Correct	48 ms	64892 KB	Output is correct
4	Correct	49 ms	64892 KB	Output is correct
5	Correct	49 ms	64892 KB	Output is correct
6	Correct	49 ms	64892 KB	Output is correct
7	Correct	49 ms	64892 KB	Output is correct
8	Correct	48 ms	64892 KB	Output is correct
9	Correct	48 ms	64892 KB	Output is correct
10	Correct	50 ms	64892 KB	Output is correct
11	Correct	53 ms	64892 KB	Output is correct
12	Correct	50 ms	64892 KB	Output is correct
13	Correct	50 ms	64892 KB	Output is correct
14	Correct	55 ms	64892 KB	Output is correct
15	Correct	54 ms	64892 KB	Output is correct
16	Correct	50 ms	64892 KB	Output is correct
17	Correct	64 ms	64892 KB	Output is correct
18	Correct	54 ms	64892 KB	Output is correct
19	Correct	52 ms	64892 KB	Output is correct
20	Correct	51 ms	64892 KB	Output is correct
21	Correct	52 ms	64892 KB	Output is correct
22	Correct	51 ms	64892 KB	Output is correct
23	Correct	55 ms	64892 KB	Output is correct
24	Correct	63 ms	64892 KB	Output is correct
25	Correct	64 ms	64892 KB	Output is correct
26	Correct	53 ms	64892 KB	Output is correct
27	Correct	55 ms	64892 KB	Output is correct
28	Correct	70 ms	64892 KB	Output is correct
29	Correct	106 ms	64892 KB	Output is correct
30	Correct	61 ms	64892 KB	Output is correct
31	Correct	79 ms	64892 KB	Output is correct
32	Correct	68 ms	64892 KB	Output is correct
33	Correct	165 ms	64892 KB	Output is correct
34	Correct	166 ms	64892 KB	Output is correct
35	Correct	173 ms	65532 KB	Output is correct
36	Correct	68 ms	65532 KB	Output is correct
37	Correct	260 ms	69324 KB	Output is correct
38	Correct	252 ms	69372 KB	Output is correct
39	Correct	251 ms	69372 KB	Output is correct
40	Correct	270 ms	69376 KB	Output is correct
41	Correct	260 ms	69500 KB	Output is correct
42	Correct	74 ms	69500 KB	Output is correct
43	Correct	71 ms	69500 KB	Output is correct
44	Correct	68 ms	69500 KB	Output is correct
45	Correct	590 ms	87980 KB	Output is correct
46	Correct	608 ms	88060 KB	Output is correct

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	48 ms	88060 KB	Output is correct
2	Correct	47 ms	88060 KB	Output is correct
3	Correct	49 ms	88060 KB	Output is correct
4	Correct	49 ms	88060 KB	Output is correct
5	Correct	58 ms	88060 KB	Output is correct
6	Correct	48 ms	88060 KB	Output is correct
7	Correct	49 ms	88060 KB	Output is correct
8	Correct	47 ms	88060 KB	Output is correct
9	Correct	48 ms	88060 KB	Output is correct
10	Correct	48 ms	88060 KB	Output is correct
11	Correct	52 ms	88060 KB	Output is correct
12	Correct	52 ms	88060 KB	Output is correct
13	Correct	49 ms	88060 KB	Output is correct
14	Correct	68 ms	88060 KB	Output is correct
15	Correct	57 ms	88060 KB	Output is correct
16	Correct	50 ms	88060 KB	Output is correct
17	Correct	62 ms	88060 KB	Output is correct
18	Correct	54 ms	88060 KB	Output is correct
19	Correct	54 ms	88060 KB	Output is correct
20	Correct	52 ms	88060 KB	Output is correct
21	Correct	50 ms	88060 KB	Output is correct
22	Correct	54 ms	88060 KB	Output is correct
23	Correct	56 ms	88060 KB	Output is correct
24	Correct	62 ms	88060 KB	Output is correct
25	Correct	57 ms	88060 KB	Output is correct
26	Correct	56 ms	88060 KB	Output is correct
27	Correct	55 ms	88060 KB	Output is correct
28	Correct	68 ms	88060 KB	Output is correct
29	Correct	101 ms	88060 KB	Output is correct
30	Correct	63 ms	88060 KB	Output is correct
31	Correct	75 ms	88060 KB	Output is correct
32	Correct	68 ms	88060 KB	Output is correct
33	Correct	167 ms	88060 KB	Output is correct
34	Correct	162 ms	88060 KB	Output is correct
35	Correct	171 ms	88060 KB	Output is correct
36	Correct	67 ms	88060 KB	Output is correct
37	Correct	250 ms	88060 KB	Output is correct
38	Correct	254 ms	88060 KB	Output is correct
39	Correct	245 ms	88060 KB	Output is correct
40	Correct	249 ms	88060 KB	Output is correct
41	Correct	263 ms	88060 KB	Output is correct
42	Correct	72 ms	88060 KB	Output is correct
43	Correct	71 ms	88060 KB	Output is correct
44	Correct	68 ms	88060 KB	Output is correct
45	Correct	576 ms	88060 KB	Output is correct
46	Correct	576 ms	88156 KB	Output is correct
47	Execution timed out	1018 ms	103440 KB	Time limit exceeded
48	Halted	0 ms	0 KB	-

답안 #48166

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
21.0 / 21.0

Subtask #5
0 / 43.0