Submission #32940

#	Time	Username	Problem	Language	Result	Execution time	Memory
32940		minimario	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	3 ms	5892 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
#define f first
#define s second
 
const int MAX = 30005;
const int SQRT = 90;
const int INF = 1000000000;
int p[MAX], len[MAX]; // position, length
 
vector<pair<int, int> > g[MAX]; 
int dist[MAX];
int targ = 0;
priority_queue<pair<int, int> > pq;

void dijk(int i) {
	dist[i] = 0;
	pq.push({0, i});
	while (!pq.empty()) {
		auto top = pq.top(); pq.pop();
		int d = -top.f;
		int loc = top.s;
		if (loc == targ) { return; }
		if (d > dist[loc]) {
			continue; 
		}
		for (auto i : g[loc]) {
			int d_new = (d + i.s);
			if (d_new < dist[i.f]) {
				dist[i.f] = d_new;
				pq.push({-d_new, i.f});
			}
		}
	}
}

map<int, bool> l[MAX], r[MAX];
int main() {
	// freopen("a.in", "r", stdin);
	// freopen("a.out", "w", stdout);
 
	int n, m; scanf("%d %d", &n, &m);
	for (int i=0; i<m; i++) {
		scanf("%d %d", &p[i], &len[i]);
		l[p[i]][len[i]] = true;
		r[p[i]][len[i]] = true;
		if (!r[p[i]][len[i]]) {
			for (int j=p[i]+len[i]; j<n; j+=len[i]) {
				r[j][len[i]] = true;
				g[p[i]].push_back({j, (j-p[i])/len[i]});
			}
		}
		if (!l[p[i]][len[i]]) {
			for (int j=p[i]-len[i]; j>=0; j-=len[i]) {
				l[j][len[i]] = true;
				g[p[i]].push_back({j, (p[i]-j)/len[i]});
			}
		}
	}
	for (int i=0; i<MAX; i++) { dist[i] = INF; }
	targ = p[1];
	dijk(p[0]);

	if (dist[p[1]] == INF) { printf("%d\n", -1); }
	else { printf("%d\n", dist[p[1]]); }
}	

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:46:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d %d", &n, &m);
                                  ^
skyscraper.cpp:48:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p[i], &len[i]);
                                 ^

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