제출 #1162218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162218		trinm01	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	797 ms	247284 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const ll MAXN = 3 * 1e4 + 1;
const ll oo = 1e9;
ll base = 320;

int n, m, b[MAXN], p[MAXN], f[MAXN][174];
vector<tuple<int, int, int>> adj[MAXN][174];

void disjktra()
{
	priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> q;
	FOR(i, 0, n + 1)
	{
		FOR(j, 0, base + 1)
		{
			f[i][j] = oo;
		}
	}
	f[b[0]][0] = 0;
	q.push({0, {b[0], 0}});
	while (q.size())
	{
		int c = q.top().fi;
		auto [nha, j] = q.top().se;
		q.pop();
		if (c > f[nha][j])
			continue;
		if (j != 0)
		{
			for (auto k = -1; k <= 1; k += 2)
			{
				if (nha + j * k >= 0 && nha + j * k < n)
				{
					int dnha = nha + j * k, dj = j, w = 1;
					if (f[dnha][dj] > f[nha][j] + w)
					{
						f[dnha][dj] = f[nha][j] + w;
						q.push({f[dnha][dj], {dnha, dj}});
					}
				}
			}
		}
		if (f[nha][0] > f[nha][j])
		{
			f[nha][0] = f[nha][j];
			q.push({f[nha][0], {nha, 0}});
		}
		for (auto [dnha, dj, w] : adj[nha][j])
		{
			if (f[dnha][dj] > f[nha][j] + w)
			{
				f[dnha][dj] = f[nha][j] + w;
				q.push({f[dnha][dj], {dnha, dj}});
			}
		}
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	if (fopen(".INP", "r"))
	{
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}

	cin >> n >> m;
	base = sqrt(n);
	FOR(i, 0, m-1)
	{
		cin >> b[i] >> p[i];
		if (p[i] >= base)
		{
			for (int k = -1; k <= 1; k += 2)
			{
				for (int j = 1; (b[i] + p[i] * j * k < n) && (b[i] + p[i] * j * k >= 0); j++)
				{
					adj[b[i]][0].push_back({b[i] + p[i] * j * k, 0, j});
				}
			}
		}
		else
		{
			adj[b[i]][0].push_back({b[i], p[i], 0});
		}
	}
	disjktra();
	if (f[b[1]][0] == oo)
		cout << -1;
	else
		cout << f[b[1]][0];

	return 0;
}

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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:78:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:79:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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