Submission #48488

#	Time	Username	Problem	Language	Result	Execution time	Memory
48488		Kmcode	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	834 ms	176180 KiB

skyscraper

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

int n;
int m;

map<pair<int, int>, vector<int> > mp;
vector<pair<int, int> > bs;
vector<int> con;
vector<int> dist;

vector<int> g[300002];

deque<int> q;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)bs.push_back(make_pair(-1, -1));
	for (int i = 0; i < n; i++)con.push_back(-1);
	for (int i = 0; i < n; i++)dist.push_back(-1);
	int idx = n;
	int star = -1;
	int en = -1;
	for (int i = 0; i < m; i++) {
		int b, p;
		scanf("%d%d", &b, &p);
		if (i == 0)star = b;
		if (i == 1)en = b;
		pair<int, int> base = make_pair(b%p, p);
		if (!mp.count(base)) {
			mp[base].clear();
			auto &v = mp[base];
			for (int pos = base.first; pos < n; pos += p) {
				v.push_back(idx);
				idx++;
				bs.push_back(base);
				con.push_back(pos);
				dist.push_back(-1);
			}
		}
		int ID = (b - base.first) / p;
		g[b].push_back(mp[base][ID]);
	}
	dist[star] = 0;
	q.push_back(star);
	while (!q.empty()) {
		int b = q.front();
		q.pop_front();
		if (b < n) {
			for (int go : g[b]) {
				if (dist[go] == -1) {
					dist[go] = dist[b];
					q.push_front(go);
				}
			}
		}
		else {
			if (con[b] != -1) {
				if (dist[con[b]] == -1) {
					dist[con[b]] = dist[b];
					q.push_front(con[b]);
				}
			}
			
				if (bs[b] == bs[b - 1]&&dist[b-1]==-1) {
					dist[b - 1] = dist[b] + 1;
					q.push_back(b - 1);
				}
				if (b + 1 < bs.size() && bs[b] == bs[b + 1] && dist[b + 1] == -1) {
					dist[b + 1] = dist[b] + 1;
					q.push_back(b + 1);
				}
		}
	}
	printf("%d\n", dist[en]);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (b + 1 < bs.size() && bs[b] == bs[b + 1] && dist[b + 1] == -1) {
         ~~~~~~^~~~~~~~~~~
skyscraper.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &b, &p);
   ~~~~~^~~~~~~~~~~~~~~~

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