제출 #48158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48158		E869120	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	1085 ms	90408 KiB

skyscraper

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
using namespace std;

long long N, M, A[30009], P[30009]; int cnt = 0;
vector<int>X[30009];
map<pair<long long, long long>, int>MM, MM2, dist; queue<pair<int, int>>Q;

void refresh(int to, int dst, int val) {
	if (to < 0 || to >= N) return;
	int F = dist[make_pair(to, dst)];
	if (F == 0) {
		dist[make_pair(to, dst)] = val;
		Q.push(make_pair(to, dst));
	}
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		cin >> A[i] >> P[i];
		long long G = A[i] % P[i]; MM2[make_pair(A[i], P[i])] = 1;
		if (MM[make_pair(G, P[i])] == 1) continue;
		MM[make_pair(G, P[i])] = 1;
		for (int j = G; j + P[i] < N; j++) {
			X[j].push_back(j + P[i]);
			X[j + P[i]].push_back(j);
		}
	}
	Q.push(make_pair(A[1], 0)); dist[make_pair(A[1], 0)] = 1;

	while (!Q.empty()) {
		pair<int, int> pos1 = Q.front(); Q.pop();
		int pos = pos1.first, state = pos1.second;

		if (state == 0) {
			for (int i = 0; i < X[pos].size(); i++) {
				int to = X[pos][i], dst = abs(pos - to); cnt++; if (MM2[make_pair(pos, dst)] == 0) continue;

				refresh(to, dst, dist[pos1] + 1);
				refresh(to, 0, dist[pos1] + 1);
			}
		}
		else {
			refresh(pos - state, state, dist[pos1] + 1);
			refresh(pos + state, state, dist[pos1] + 1);
			refresh(pos - state, 0, dist[pos1] + 1);
			refresh(pos + state, 0, dist[pos1] + 1);
		}
	}
	cout << dist[make_pair(A[2], 0)] - 1 << endl;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < X[pos].size(); i++) {
                    ~~^~~~~~~~~~~~~~~

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