답안 #15877 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15877	2015-07-31T18:45:27 Z	myungwoo	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	2 ms	8400 KB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define MAXN 30005
#define pb push_back
#define mp make_pair
typedef pair<int, int> pii;

int N, M, S, E;
int D[MAXN];
bool V[MAXN][200];
vector <int> doge[MAXN];

int main()
{
	scanf("%d%d", &N, &M);
	for (int i=0;i<M;i++){
		int b, p;
		scanf("%d%d", &b, &p);
		if (p > 199 || !V[b][p]) doge[b].pb(p);
		V[b][p] = 1;
		if (!i) S = b;
		if (i == 1) E = b;
	}
	for (int i=0;i<N;i++) D[i] = 2e9;
	priority_queue <pii> que;
	D[S] = 0;
	que.push(mp(0, S));
	while (!que.empty()){
		int q = que.top().second, d = -que.top().first; que.pop();
		if (D[q] != d) continue;
		for (int p: doge[q]){
			for (int i=q-p;i>=0;i-=p){
				if (D[i] > d+(q-i)/p)
					D[i] = d+(q-i)/p, que.push(mp(-D[i], i));
				if (p < 200 && V[i][p]) break;
			}
			for (int i=q+p;i<N;i+=p){
				if (D[i] > d+(i-q)/p)
					D[i] = d+(i-q)/p, que.push(mp(-D[i], i));
				if (p < 200 && V[i][p]) break;
			}
		}
	}
	printf("%d\n", D[E] < 2e9 ? D[E] : -1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

#	결과	메모리	Grader output
1	Correct	8400 KB	Output is correct
2	Correct	8400 KB	Output is correct
3	Correct	8400 KB	Output is correct
4	Correct	8400 KB	Output is correct
5	Correct	8400 KB	Output is correct
6	Correct	8400 KB	Output is correct
7	Correct	8400 KB	Output is correct
8	Correct	8400 KB	Output is correct
9	Correct	8400 KB	Output is correct
10	Correct	8400 KB	Output is correct
11	Correct	8400 KB	Output is correct
12	Correct	8400 KB	Output is correct
13	Correct	8400 KB	Output is correct
14	Correct	8400 KB	Output is correct
15	Correct	8400 KB	Output is correct

Subtask #3
0.0 / 14.0

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

Subtask #4
0.0 / 21.0

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

Subtask #5
0.0 / 43.0

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

답안 #15877

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 0.0 / 14.0

Subtask #4 0.0 / 21.0

Subtask #5 0.0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
0.0 / 14.0

Subtask #4
0.0 / 21.0

Subtask #5
0.0 / 43.0