oj.uz

답안 #733592

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
733592 2023-05-01T04:23:34 Z SanguineChameleon Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 159 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, int>> 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

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 235140 KB Output is correct
2 Correct 114 ms 235148 KB Output is correct
3 Correct 111 ms 235120 KB Output is correct
4 Correct 109 ms 235092 KB Output is correct
5 Correct 109 ms 235036 KB Output is correct
6 Correct 114 ms 235048 KB Output is correct
7 Correct 112 ms 235224 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 235060 KB Output is correct
2 Correct 108 ms 235128 KB Output is correct
3 Correct 111 ms 235192 KB Output is correct
4 Correct 106 ms 235048 KB Output is correct
5 Correct 106 ms 235144 KB Output is correct
6 Correct 105 ms 235144 KB Output is correct
7 Correct 107 ms 235164 KB Output is correct
8 Correct 114 ms 235156 KB Output is correct
9 Correct 110 ms 235184 KB Output is correct
10 Correct 113 ms 235212 KB Output is correct
11 Correct 117 ms 235612 KB Output is correct
12 Correct 146 ms 245180 KB Output is correct
13 Correct 144 ms 245340 KB Output is correct
14 Correct 108 ms 235408 KB Output is correct
15 Correct 108 ms 235404 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 235064 KB Output is correct
2 Correct 108 ms 235180 KB Output is correct
3 Correct 122 ms 235084 KB Output is correct
4 Correct 107 ms 235148 KB Output is correct
5 Correct 111 ms 235160 KB Output is correct
6 Correct 108 ms 235096 KB Output is correct
7 Correct 110 ms 235072 KB Output is correct
8 Correct 107 ms 235108 KB Output is correct
9 Correct 111 ms 235132 KB Output is correct
10 Correct 117 ms 235212 KB Output is correct
11 Correct 109 ms 235664 KB Output is correct
12 Correct 144 ms 245128 KB Output is correct
13 Correct 155 ms 245328 KB Output is correct
14 Correct 114 ms 235428 KB Output is correct
15 Correct 114 ms 235404 KB Output is correct
16 Correct 146 ms 235380 KB Output is correct
17 Correct 112 ms 236312 KB Output is correct
18 Correct 109 ms 235476 KB Output is correct
19 Correct 108 ms 235412 KB Output is correct
20 Runtime error 150 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 235036 KB Output is correct
2 Correct 107 ms 235148 KB Output is correct
3 Correct 126 ms 235040 KB Output is correct
4 Correct 119 ms 235056 KB Output is correct
5 Correct 112 ms 235036 KB Output is correct
6 Correct 109 ms 235116 KB Output is correct
7 Correct 112 ms 235156 KB Output is correct
8 Correct 110 ms 235148 KB Output is correct
9 Correct 111 ms 235164 KB Output is correct
10 Correct 111 ms 235148 KB Output is correct
11 Correct 111 ms 235652 KB Output is correct
12 Correct 159 ms 245152 KB Output is correct
13 Correct 157 ms 245236 KB Output is correct
14 Correct 115 ms 235368 KB Output is correct
15 Correct 108 ms 235420 KB Output is correct
16 Correct 112 ms 235340 KB Output is correct
17 Correct 116 ms 236260 KB Output is correct
18 Correct 109 ms 235460 KB Output is correct
19 Correct 108 ms 235296 KB Output is correct
20 Runtime error 147 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 235084 KB Output is correct
2 Correct 113 ms 235164 KB Output is correct
3 Correct 108 ms 235124 KB Output is correct
4 Correct 109 ms 235088 KB Output is correct
5 Correct 108 ms 235120 KB Output is correct
6 Correct 120 ms 235132 KB Output is correct
7 Correct 108 ms 235084 KB Output is correct
8 Correct 109 ms 235084 KB Output is correct
9 Correct 109 ms 235100 KB Output is correct
10 Correct 109 ms 235172 KB Output is correct
11 Correct 110 ms 235668 KB Output is correct
12 Correct 144 ms 245180 KB Output is correct
13 Correct 147 ms 245452 KB Output is correct
14 Correct 110 ms 235360 KB Output is correct
15 Correct 108 ms 235344 KB Output is correct
16 Correct 111 ms 235384 KB Output is correct
17 Correct 121 ms 236224 KB Output is correct
18 Correct 109 ms 235420 KB Output is correct
19 Correct 119 ms 235364 KB Output is correct
20 Runtime error 149 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -