oj.uz

Submission #733594

# Submission time Handle Problem Language Result Execution time Memory
733594 2023-05-01T04:25:52 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 152 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 = 1e7 + 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 110 ms 235036 KB Output is correct
2 Correct 105 ms 235052 KB Output is correct
3 Correct 106 ms 235032 KB Output is correct
4 Correct 106 ms 235084 KB Output is correct
5 Correct 108 ms 235084 KB Output is correct
6 Correct 108 ms 235068 KB Output is correct
7 Correct 109 ms 235120 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 235100 KB Output is correct
2 Correct 118 ms 235144 KB Output is correct
3 Correct 108 ms 235068 KB Output is correct
4 Correct 116 ms 235144 KB Output is correct
5 Correct 107 ms 235120 KB Output is correct
6 Correct 115 ms 235136 KB Output is correct
7 Correct 109 ms 235172 KB Output is correct
8 Correct 114 ms 235108 KB Output is correct
9 Correct 103 ms 235100 KB Output is correct
10 Correct 108 ms 235232 KB Output is correct
11 Correct 108 ms 235596 KB Output is correct
12 Correct 151 ms 245144 KB Output is correct
13 Correct 145 ms 245320 KB Output is correct
14 Correct 111 ms 235528 KB Output is correct
15 Correct 112 ms 235444 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 235132 KB Output is correct
2 Correct 114 ms 235060 KB Output is correct
3 Correct 107 ms 235084 KB Output is correct
4 Correct 109 ms 235136 KB Output is correct
5 Correct 107 ms 235020 KB Output is correct
6 Correct 120 ms 235084 KB Output is correct
7 Correct 111 ms 235148 KB Output is correct
8 Correct 113 ms 235124 KB Output is correct
9 Correct 118 ms 235160 KB Output is correct
10 Correct 109 ms 235268 KB Output is correct
11 Correct 120 ms 235628 KB Output is correct
12 Correct 144 ms 245196 KB Output is correct
13 Correct 141 ms 245312 KB Output is correct
14 Correct 107 ms 235412 KB Output is correct
15 Correct 108 ms 235420 KB Output is correct
16 Correct 121 ms 235364 KB Output is correct
17 Correct 111 ms 236216 KB Output is correct
18 Correct 108 ms 235468 KB Output is correct
19 Correct 110 ms 235344 KB Output is correct
20 Runtime error 145 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 111 ms 235140 KB Output is correct
2 Correct 109 ms 235092 KB Output is correct
3 Correct 108 ms 235092 KB Output is correct
4 Correct 106 ms 235036 KB Output is correct
5 Correct 111 ms 235112 KB Output is correct
6 Correct 108 ms 235108 KB Output is correct
7 Correct 107 ms 235096 KB Output is correct
8 Correct 107 ms 235048 KB Output is correct
9 Correct 108 ms 235100 KB Output is correct
10 Correct 108 ms 235256 KB Output is correct
11 Correct 113 ms 235652 KB Output is correct
12 Correct 138 ms 245196 KB Output is correct
13 Correct 141 ms 245244 KB Output is correct
14 Correct 110 ms 235424 KB Output is correct
15 Correct 107 ms 235412 KB Output is correct
16 Correct 109 ms 235340 KB Output is correct
17 Correct 112 ms 236232 KB Output is correct
18 Correct 116 ms 235544 KB Output is correct
19 Correct 118 ms 235352 KB Output is correct
20 Runtime error 152 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 118 ms 235136 KB Output is correct
2 Correct 120 ms 235140 KB Output is correct
3 Correct 116 ms 235052 KB Output is correct
4 Correct 114 ms 235256 KB Output is correct
5 Correct 110 ms 235084 KB Output is correct
6 Correct 111 ms 235048 KB Output is correct
7 Correct 110 ms 235068 KB Output is correct
8 Correct 113 ms 235084 KB Output is correct
9 Correct 111 ms 235116 KB Output is correct
10 Correct 110 ms 235244 KB Output is correct
11 Correct 108 ms 235544 KB Output is correct
12 Correct 142 ms 245200 KB Output is correct
13 Correct 143 ms 245252 KB Output is correct
14 Correct 119 ms 235340 KB Output is correct
15 Correct 117 ms 235360 KB Output is correct
16 Correct 107 ms 235324 KB Output is correct
17 Correct 116 ms 236276 KB Output is correct
18 Correct 109 ms 235412 KB Output is correct
19 Correct 108 ms 235436 KB Output is correct
20 Runtime error 137 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -