oj.uz

Submission #733595

# Submission time Handle Problem Language Result Execution time Memory
733595 2023-05-01T04:26:27 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 330 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxN = 3e4 + 20;
const int maxC = 5e6 + 20;
const int inf = 1e9 + 20;
int B[maxN];
int P[maxN];
vector<pair<int, bool>> adj[maxC];
int dist[maxC];

void just_do_it() {
	int N, M;
	cin >> N >> M;
	const int lim = 0;
	int cnt = N;
	for (int i = 0; i < M; i++) {
		cin >> B[i] >> P[i];
		if (P[i] > lim) {
			int cur = B[i] % P[i];
			int nxt = cur + P[i];
			for (; cur < N; cur += P[i], nxt += P[i]) {
				if (nxt < N) {
					adj[cnt].emplace_back(cnt + 1, 1);
					adj[cnt + 1].emplace_back(cnt, 1);
				}
				if (cur == B[i]) {
					adj[B[i]].emplace_back(cnt, 0);
				}
				adj[cnt].emplace_back(cur, 0);
				cnt++;
			}
		}
	}
	assert(cnt < maxC);
	for (int i = 0; i < cnt; i++) {
		dist[i] = inf;
	}
	dist[B[0]] = 0;
	deque<int> q = {B[0]};
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		for (auto p: adj[u]) {
			int v = p.first;
			int w = p.second;
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				if (w == 0) {
					q.push_front(v);
				}
				else {
					q.push_back(v);
				}
			}
		}
	}
	if (dist[B[1]] == inf) {
		cout << -1;
	}
	else {
		cout << dist[B[1]];
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117708 KB Output is correct
2 Correct 66 ms 117616 KB Output is correct
3 Correct 63 ms 117708 KB Output is correct
4 Correct 60 ms 117656 KB Output is correct
5 Correct 63 ms 117684 KB Output is correct
6 Correct 59 ms 117664 KB Output is correct
7 Correct 60 ms 117656 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 117612 KB Output is correct
2 Correct 61 ms 117708 KB Output is correct
3 Correct 60 ms 117728 KB Output is correct
4 Correct 54 ms 117708 KB Output is correct
5 Correct 57 ms 117612 KB Output is correct
6 Correct 59 ms 117732 KB Output is correct
7 Correct 62 ms 117612 KB Output is correct
8 Correct 59 ms 117624 KB Output is correct
9 Correct 58 ms 117648 KB Output is correct
10 Correct 57 ms 117836 KB Output is correct
11 Correct 60 ms 118224 KB Output is correct
12 Correct 90 ms 127784 KB Output is correct
13 Correct 90 ms 127908 KB Output is correct
14 Correct 61 ms 117984 KB Output is correct
15 Correct 58 ms 117968 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 117716 KB Output is correct
2 Correct 63 ms 117732 KB Output is correct
3 Correct 57 ms 117728 KB Output is correct
4 Correct 64 ms 117708 KB Output is correct
5 Correct 57 ms 117676 KB Output is correct
6 Correct 56 ms 117692 KB Output is correct
7 Correct 56 ms 117672 KB Output is correct
8 Correct 56 ms 117668 KB Output is correct
9 Correct 55 ms 117708 KB Output is correct
10 Correct 62 ms 117844 KB Output is correct
11 Correct 58 ms 118232 KB Output is correct
12 Correct 87 ms 127680 KB Output is correct
13 Correct 90 ms 127880 KB Output is correct
14 Correct 57 ms 117936 KB Output is correct
15 Correct 58 ms 117964 KB Output is correct
16 Correct 57 ms 117908 KB Output is correct
17 Correct 60 ms 118860 KB Output is correct
18 Correct 56 ms 118052 KB Output is correct
19 Correct 59 ms 117988 KB Output is correct
20 Runtime error 312 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117708 KB Output is correct
2 Correct 58 ms 117716 KB Output is correct
3 Correct 64 ms 117648 KB Output is correct
4 Correct 56 ms 117636 KB Output is correct
5 Correct 56 ms 117648 KB Output is correct
6 Correct 55 ms 117628 KB Output is correct
7 Correct 57 ms 117680 KB Output is correct
8 Correct 58 ms 117708 KB Output is correct
9 Correct 62 ms 117712 KB Output is correct
10 Correct 59 ms 117752 KB Output is correct
11 Correct 62 ms 118124 KB Output is correct
12 Correct 89 ms 127688 KB Output is correct
13 Correct 93 ms 127900 KB Output is correct
14 Correct 58 ms 117940 KB Output is correct
15 Correct 62 ms 118004 KB Output is correct
16 Correct 57 ms 118032 KB Output is correct
17 Correct 67 ms 118832 KB Output is correct
18 Correct 55 ms 118088 KB Output is correct
19 Correct 56 ms 117964 KB Output is correct
20 Runtime error 317 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 117708 KB Output is correct
2 Correct 57 ms 117620 KB Output is correct
3 Correct 61 ms 117680 KB Output is correct
4 Correct 57 ms 117668 KB Output is correct
5 Correct 57 ms 117692 KB Output is correct
6 Correct 61 ms 117652 KB Output is correct
7 Correct 57 ms 117732 KB Output is correct
8 Correct 59 ms 117680 KB Output is correct
9 Correct 56 ms 117712 KB Output is correct
10 Correct 57 ms 117724 KB Output is correct
11 Correct 59 ms 118332 KB Output is correct
12 Correct 91 ms 127772 KB Output is correct
13 Correct 91 ms 127844 KB Output is correct
14 Correct 57 ms 118040 KB Output is correct
15 Correct 58 ms 117984 KB Output is correct
16 Correct 57 ms 117992 KB Output is correct
17 Correct 60 ms 118796 KB Output is correct
18 Correct 59 ms 118112 KB Output is correct
19 Correct 57 ms 117988 KB Output is correct
20 Runtime error 330 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -