Submission #103860

#	Time	Username	Problem	Language	Result	Execution time	Memory
103860		E869120	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	354 ms	154116 KiB

skyscraper

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
using namespace std;
#pragma warning (disable: 4996)

const int MAX_N = 1000000;

vector<pair<int, int>>X[30009]; map<int, int>Map[30009], Map2[30009];
int N, M, B[30009], P[30009], dist[30009], cntv; unsigned int Z[35000000];
vector<int>Q[MAX_N];

int check(int p1, int p2) {
	if ((Z[p1 * 1024 + (p2 >> 5)] & (1U << (p2 & 31))) == 0) return 0;
	return 1;
}

int main() {
	srand((unsigned)time(NULL));
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		scanf("%d%d", &B[i], &P[i]);
		Z[(B[i] * 1024 + (P[i] >> 5))] |= (1U << (P[i] & 31));
	}
	for (int i = 0; i < M; i++) {
		if (Map2[B[i]][P[i]] == 1) continue;
		int cnt = 0;
		for (int j = B[i] - P[i]; j >= 0; j -= P[i]) {
			cnt++;
			X[B[i]].push_back(make_pair(j, cnt)); cntv++;
			if (check(j, P[i]) == 1) break;
		}
		cnt = 0;
		for (int j = B[i] + P[i]; j < N; j += P[i]) {
			cnt++;
			X[B[i]].push_back(make_pair(j, cnt)); cntv++;
			if (check(j, P[i]) == 1) break;
		}
		Map2[B[i]][P[i]] = 1;
	}

	for (int i = 0; i < N; i++) dist[i] = (1 << 30);
	dist[B[0]] = 0; Q[0].push_back(B[0]);

	cntv = 0;
	for (int i = 0; i < MAX_N - 1; i++) {
		for (int j = 0; j < Q[i].size(); j++) {
			int pos = Q[i][j];
			for (int k = 0; k < X[pos].size(); k++) {
				int to = X[pos][k].first, cost = X[pos][k].second;
				if (dist[to] > dist[pos] + cost) {
					dist[to] = dist[pos] + cost;
					Q[dist[to]].push_back(to);
				}
			}
		}
		cntv += Q[i].size();
	}

	if (dist[B[1]] == (1 << 30)) cout << "-1" << endl;
	else cout << dist[B[1]] << endl;
	return 0;
}

Compilation message (stderr)

skyscraper.cpp:8:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < Q[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
skyscraper.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < X[pos].size(); k++) {
                    ~~^~~~~~~~~~~~~~~
skyscraper.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &B[i], &P[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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