oj.uz

답안 #771292

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771292 2023-07-02T19:30:20 Z IBory Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 1 ms 1108 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 30003;
vector<pii> G[MAX];
int D[MAX];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, S, E;
	cin >> N >> M;
	map<pii, vector<int>> make;
	for (int i = 0; i < M; ++i) {
		int b, p;
		cin >> b >> p;
		if (i == 0) S = b;
		if (i == 1) E = b;
		make[{p, b % p}].push_back(b);
	}

	for (auto& [q, v] : make) {
		auto [p, init] = q;
		v.push_back(init);
		v.push_back(init + (N - 1 - init) / p * p);
		sort(v.begin(), v.end());
		for (int i = 1; i + 1 < v.size(); ++i) {
			int n = v[i] - p, d = 1;
			while (n >= v[i - 1]) {
				G[v[i]].emplace_back(n, d++);
				n -= p;
			}
			n = v[i] + p, d = 1;
			while (n <= v[i + 1]) {
				G[v[i]].emplace_back(n, d++);
				n += p;
			}
		}
	}

	memset(D, 0x3f, sizeof(D));
	priority_queue<pii, vector<pii>, greater<pii>> PQ; 
	PQ.emplace(D[S] = S, S);
	while (!PQ.empty()) {
		auto [cd, cur] = PQ.top(); PQ.pop();
		if (cd > D[cur]) continue;
		if (cur == E) break;
		for (auto [next, nd] : G[cur]) {
			if (cd + nd >= D[next]) continue;
			PQ.emplace(D[next] = cd + nd, next);
		}
	}

	cout << (D[E] > 1E9 ? -1 : D[E]);
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:31:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (int i = 1; i + 1 < v.size(); ++i) {
      |                   ~~~~~~^~~~~~~~~~
skyscraper.cpp:51:3: warning: 'E' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |   if (cur == E) break;
      |   ^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Incorrect 1 ms 1108 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Incorrect 1 ms 1108 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Incorrect 1 ms 1108 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1040 KB Output is correct
8 Incorrect 1 ms 1108 KB Output isn't correct
9 Halted 0 ms 0 KB -