oj.uz

Submission #15873

# Submission time Handle Problem Language Result Execution time Memory
15873 2015-07-31T18:11:59 Z myungwoo Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 293 ms 23164 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -