제출 #499350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
499350		pavement	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	86 ms	10956 KiB

skyscraper

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
//#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int C = 300;
bool has[30005][305];
int N, M, st, ed, dist[30005];
vector<int> dog[30005];
priority_queue<ii, vector<ii>, greater<ii> > pq;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0, B, P; i < M; i++) {
		cin >> B >> P;
		if (P <= C && !has[B][P]) {
			has[B][P] = 1;
			dog[B].eb(P);
		} else if (P > C) {
			dog[B].pb(P);
		}
		if (i == 0) st = B;
		else if (i == 1) ed = B;
	}
	for (int i = 0; i < N; i++) dist[i] = 1e9;
	dist[st] = 0;
	pq.emplace(0, st);
	while (!pq.empty()) {
		auto [d, v] = pq.top();
		pq.pop();
		if (dist[v] != d) continue;
		for (auto u : dog[v]) {
			for (int i = v - u; i >= 0; i -= u) {
				if (dist[i] > d + (v - i) / u) {
					dist[i] = d + (v - i) / u;
					pq.emplace(dist[i], i);
				}
				if (u <= C && has[i][u]) break;
			}
			for (int i = v + u; i < N; i += u) {
				if (dist[i] > d + (i - v) / u) {
					dist[i] = d + (i - v) / u;
					pq.emplace(dist[i], i);
				}
				if (u <= C && has[i][u]) break;
			}
		}
	}
	cout << (dist[ed] == 1e9 ? -1 : dist[ed]) << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main() {
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43