Submission #108316

#	Time	Username	Problem	Language	Result	Execution time	Memory
108316		kek	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	221 ms	263168 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

// #define int ll
#define all(v) v.begin(), v.end()
#define len(v) ((int)(v).size())
#define pb push_back
#define kek pop_back
#define pii pair<int, int>
#define mp make_pair

#define debug(x) cout << #x << " = " << x << endl;

const int INF = 1e9 + 666;

template<class t1, class t2>
bool cmin(t1 &a, const t2 &b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template<class t1, class t2>
bool cmax(t1 &a, const t2 &b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

#ifndef LOCAL
void UseFiles(const string &s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}
#else
void UseFiles(const string&) {}
#endif

void run();

signed main() {
	// UseFiles("cowboys");
	iostream::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
}

void run() {
	int n, m;
	cin >> n >> m;
	vector<pii> doges(m);
	swap(n, m);
	for (auto &x : doges) {
		cin >> x.first >> x.second;
	}
	vector<vector<int>> g(n, vector<int>(n, INF));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if ((doges[i].first - doges[j].first) % doges[i].second == 0) {
				g[i][j] = abs((doges[i].first - doges[j].first) / doges[i].second);
			}
		}
	}
	vector<int> dist(n, INF);
	dist[0] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> q;
	q.push({0, 0});
	while (len(q)) {
		int d, v;
		tie(d, v) = q.top();
		q.pop();
		if (dist[v] != d) {
			continue;
		}
		for (int i = 0; i < n; ++i) {
			if (cmin(dist[i], d + g[v][i])) {
				q.push({dist[i], i});
			}
		}
	}
	if (dist[1] == INF) {
		cout << -1 << endl;
	} else {
		cout << dist[1] << endl;
	}
}

Compilation message (stderr)

skyscraper.cpp: In function 'void UseFiles(const string&)':
skyscraper.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((s + ".in").c_str(), "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((s + ".out").c_str(), "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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