oj.uz

Submission #733598

# Submission time Handle Problem Language Result Execution time Memory
733598 2023-05-01T04:27:35 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 171 ms 143112 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 = 1e6 + 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 13 ms 23732 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23820 KB Output is correct
5 Correct 14 ms 23780 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23820 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23708 KB Output is correct
6 Correct 11 ms 23752 KB Output is correct
7 Correct 13 ms 23808 KB Output is correct
8 Correct 13 ms 23712 KB Output is correct
9 Correct 12 ms 23804 KB Output is correct
10 Correct 13 ms 23824 KB Output is correct
11 Correct 14 ms 24276 KB Output is correct
12 Correct 46 ms 33860 KB Output is correct
13 Correct 45 ms 33932 KB Output is correct
14 Correct 13 ms 24120 KB Output is correct
15 Correct 15 ms 24112 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23788 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23700 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23796 KB Output is correct
6 Correct 15 ms 23724 KB Output is correct
7 Correct 13 ms 23824 KB Output is correct
8 Correct 12 ms 23760 KB Output is correct
9 Correct 13 ms 23764 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 15 ms 24276 KB Output is correct
12 Correct 47 ms 33848 KB Output is correct
13 Correct 47 ms 33968 KB Output is correct
14 Correct 13 ms 24020 KB Output is correct
15 Correct 16 ms 24080 KB Output is correct
16 Correct 14 ms 24020 KB Output is correct
17 Correct 17 ms 24880 KB Output is correct
18 Correct 13 ms 24148 KB Output is correct
19 Correct 13 ms 24020 KB Output is correct
20 Runtime error 155 ms 143060 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23820 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 14 ms 23708 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 14 ms 23952 KB Output is correct
11 Correct 14 ms 24228 KB Output is correct
12 Correct 46 ms 33748 KB Output is correct
13 Correct 47 ms 33976 KB Output is correct
14 Correct 14 ms 24020 KB Output is correct
15 Correct 14 ms 24104 KB Output is correct
16 Correct 14 ms 24020 KB Output is correct
17 Correct 16 ms 24860 KB Output is correct
18 Correct 13 ms 24156 KB Output is correct
19 Correct 13 ms 24004 KB Output is correct
20 Runtime error 163 ms 143112 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23732 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23776 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 14 ms 23764 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 13 ms 23708 KB Output is correct
9 Correct 13 ms 23764 KB Output is correct
10 Correct 13 ms 23820 KB Output is correct
11 Correct 16 ms 24220 KB Output is correct
12 Correct 46 ms 33820 KB Output is correct
13 Correct 49 ms 33912 KB Output is correct
14 Correct 13 ms 24020 KB Output is correct
15 Correct 13 ms 24020 KB Output is correct
16 Correct 13 ms 24020 KB Output is correct
17 Correct 16 ms 24916 KB Output is correct
18 Correct 14 ms 24148 KB Output is correct
19 Correct 13 ms 24076 KB Output is correct
20 Runtime error 171 ms 143108 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -