제출 #1130904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130904		am_aadvik	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	568 ms	327680 KiB

skyscraper

#include <iostream>
#include<vector>
#include<math.h>
#include<set>
const int inf = 1e9;
const int tlim = 6e6;
const int sl = 180;
#define f(x, y) x * sl + y
using namespace std;

vector<pair<int, int>> g[tlim]; //pos = node,power (= 0 if js node) node*sl+power
set<pair<int, int>> q; //{dist, pos}
vector<int> dist;
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n, m, s = -1, sq, t = -1; cin >> n >> m;
	sq = sqrt(n);

	for (int i = 0; i < n; ++i)
		for (int j = 1; j <= sq; ++j)
			g[f(i, j)].push_back({ 180 * i,0 });

	for (int i = 0; i < n; ++i)
		for (int j = 1; j <= sq; ++j) {
			if (i >= j) g[f(i, j)].push_back({f((i - j), j), 1});
			if ((i + j) < n) g[f(i, j)].push_back({ f((i + j), j), 1 });
		}

	for (int i = 0; i < m; ++i) {
		int x, y; cin >> x >> y;
		if (i == 0) s = sl * x;
		if (i == 1) t = sl * x;
		if (y > sq) {
			if(x >= y)
			for (int i = x - y, v = 1; i >= 0; i -= y, ++v)
				g[180 * x].push_back({ 180 * i, v });
			if((x + y) < n)
			for (int i = x + y, v = 1; i < n; i += y, ++v)
				g[180 * x].push_back({ 180 * i, v });
		}
		else
			g[180 * x].push_back({ f(x,y), 0 });
	}

	dist.assign(tlim, inf);
	dist[s] = 0;
	q.insert({ 0, s });
	while (q.size()) {
		auto x = *q.begin(); q.erase(q.begin());
		if (x.second == t) { cout << x.first; return 0; }
		for (auto y : g[x.second])
			if (dist[y.first] > (x.first + y.second)) {
				if (dist[y.first] < inf) q.erase({ dist[y.first], y.first });
				dist[y.first] = (x.first + y.second);
				q.insert({ dist[y.first], y.first });
			}
	}
	cout << -1;
}

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