답안 #15873 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15873	2015-07-31T18:11:59 Z	myungwoo	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	293 ms	23164 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];
set <int> A[200][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); doge[b].pb(p);
		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));
	for (int i=0;i<N;i++) for (int j=1;j<200;j++) A[j][i%j].insert(i);
	while (!que.empty()){
		int q = que.top().second, d = -que.top().first; que.pop();
		if (D[q] != d) continue;
		if (q == E) break;
		for (int i=1;i<200;i++) A[i][q%i].erase(q);
		for (int p: doge[q]){
			if (p > 199){
				for (int i=q-p;i>=0;i-=p)
					if (D[i] > D[q]+(q-i)/p)
						D[i] = D[q]+(q-i)/p, que.push(mp(-D[i], i));
			}else{
				int m = q % p;
				for (auto it=A[p][m].begin();it!=A[p][m].end();it++){
					if (D[*it] > D[q]+abs(*it-q)/p)
						D[*it] = D[q]+abs(*it-q)/p, que.push(mp(-D[*it], *it));
				}
			}
		}
	}
	printf("%d\n", D[E] < 2e9 ? D[E] : -1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
0.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4420 KB	Output is correct
2	Correct	0 ms	4420 KB	Output is correct
3	Correct	0 ms	4420 KB	Output is correct
4	Correct	0 ms	4420 KB	Output is correct
5	Correct	0 ms	4420 KB	Output is correct
6	Correct	0 ms	4420 KB	Output is correct
7	Correct	0 ms	4420 KB	Output is correct
8	Correct	3 ms	4684 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	5344 KB	Output is correct
11	Correct	0 ms	5344 KB	Output is correct
12	Correct	2 ms	5344 KB	Output is correct
13	Correct	0 ms	5344 KB	Output is correct
14	Correct	5 ms	5344 KB	Output is correct
15	Correct	0 ms	5344 KB	Output is correct
16	Correct	7 ms	6268 KB	Output is correct
17	Correct	54 ms	11284 KB	Output is correct
18	Correct	126 ms	20656 KB	Output is correct
19	Correct	153 ms	23032 KB	Output is correct
20	Correct	293 ms	23164 KB	Output is correct
21	Correct	14 ms	7984 KB	Output is correct
22	Correct	129 ms	21052 KB	Output is correct
23	Incorrect	116 ms	19336 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4420 KB	Output is correct
2	Correct	0 ms	4420 KB	Output is correct
3	Correct	2 ms	4420 KB	Output is correct
4	Correct	0 ms	4420 KB	Output is correct
5	Correct	0 ms	4420 KB	Output is correct
6	Correct	0 ms	4420 KB	Output is correct
7	Correct	2 ms	4420 KB	Output is correct
8	Correct	0 ms	4684 KB	Output is correct
9	Correct	0 ms	4948 KB	Output is correct
10	Correct	0 ms	5344 KB	Output is correct
11	Correct	0 ms	5344 KB	Output is correct
12	Correct	0 ms	5344 KB	Output is correct
13	Correct	5 ms	5344 KB	Output is correct
14	Correct	0 ms	5344 KB	Output is correct
15	Correct	5 ms	5344 KB	Output is correct
16	Correct	0 ms	6268 KB	Output is correct
17	Correct	45 ms	11284 KB	Output is correct
18	Correct	125 ms	20656 KB	Output is correct
19	Correct	155 ms	23032 KB	Output is correct
20	Correct	275 ms	23164 KB	Output is correct
21	Correct	5 ms	7984 KB	Output is correct
22	Correct	128 ms	21052 KB	Output is correct
23	Incorrect	101 ms	19336 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4420 KB	Output is correct
2	Correct	0 ms	4420 KB	Output is correct
3	Correct	0 ms	4420 KB	Output is correct
4	Correct	0 ms	4420 KB	Output is correct
5	Correct	0 ms	4420 KB	Output is correct
6	Correct	0 ms	4420 KB	Output is correct
7	Correct	0 ms	4420 KB	Output is correct
8	Correct	2 ms	4684 KB	Output is correct
9	Correct	0 ms	4948 KB	Output is correct
10	Correct	4 ms	5344 KB	Output is correct
11	Correct	0 ms	5344 KB	Output is correct
12	Correct	0 ms	5344 KB	Output is correct
13	Correct	5 ms	5344 KB	Output is correct
14	Correct	3 ms	5344 KB	Output is correct
15	Correct	4 ms	5344 KB	Output is correct
16	Correct	7 ms	6268 KB	Output is correct
17	Correct	41 ms	11284 KB	Output is correct
18	Correct	121 ms	20656 KB	Output is correct
19	Correct	155 ms	23032 KB	Output is correct
20	Correct	275 ms	23164 KB	Output is correct
21	Correct	11 ms	7984 KB	Output is correct
22	Correct	130 ms	21052 KB	Output is correct
23	Incorrect	121 ms	19336 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

답안 #15873

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