Submission #312168

#	Time	Username	Problem	Language	Result	Execution time	Memory
312168		hoaphat1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	140 ms	6000 KiB

skyscraper

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

void fff(string s = "") {
	cin >> s;
	if ((int)s.size() >= 4) {
		freopen(s.c_str(),"r",stdin);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	#ifdef LOCAL 
	fff();
	#endif
	int n,m;
	cin >> n >> m;
	vector<pair<int,int>> a(m);
	vector<vector<int>> inner(n);
	for (int i = 0; i < m; i++) {
		cin >> a[i].first >> a[i].second;
		inner[a[i].first].push_back(a[i].second);
	}
	for (int i = 0; i < n; i++) {
		sort(inner[i].begin(),inner[i].end());
		inner[i].resize(unique(inner[i].begin(),inner[i].end()) - inner[i].begin());
	}
	const int inf = (int)2e9;
	vector<int> d(n,inf);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	d[a[0].first] = 0;
	pq.emplace(0,a[0].first);
	while ((int)pq.size()) {
		auto x = pq.top();pq.pop();
		if (x.first != d[x.second]) continue;
		for (auto&step : inner[x.second]) {
			for (int num = 1; x.second + num * step < n; num++) {
				int nxt = x.second + num * step;
				if (d[nxt] > x.first + num) {
					d[nxt] = x.first + num;
					pq.emplace(d[nxt],nxt);
				}
				auto it = lower_bound(inner[nxt].begin(),inner[nxt].end(),step);
				if (it != inner[nxt].end() && *it == step) {
					break;
				}
			}	
			for (int num = 1; x.second - num * step >= 0; num++) {
				int nxt = x.second - num * step;
				if (d[nxt] > x.first + num) {
					d[nxt] = x.first + num;
					pq.emplace(d[nxt],nxt);
				}
				auto it = lower_bound(inner[nxt].begin(),inner[nxt].end(),step);
				if (it != inner[nxt].end() && *it == step) {
					break;
				}
			}
		}
	}
	if (d[a[1].first] == inf) d[a[1].first] = -1;
	cout << d[a[1].first];
} 

Compilation message (stderr)

skyscraper.cpp: In function 'void fff(std::string)':
skyscraper.cpp:8:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    8 |   freopen(s.c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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