oj.uz

Submission #48173

# Submission time Handle Problem Language Result Execution time Memory
48173 2018-05-10T12:38:58 Z E869120 Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 4 ms 2692 KB 
#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;

int N, M, A[30009], P[30009]; vector<int>G[30009], dist[30009]; vector<vector<pair<int, int>>> X[30009];
map<pair<int, int>, int>M1; queue<pair<int, int>>Q;

void connect(int px, int py, int qx, int qy) {
	X[px][py].push_back(make_pair(qx, qy));
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) G[0].push_back(i);
	X[0].resize(G[0].size());
	dist[0].resize(G[0].size(), (1 << 30));
	for (int i = 1; i <= M; i++) {
		cin >> A[i] >> P[i];
		int J = M1[make_pair(A[i] % P[i], P[i])];
		if (J == 0) {
			M1[make_pair(A[i] % P[i], P[i])] = i; J = i;
			for (int j = A[i] % P[i]; j < N; j += P[i]) G[i].push_back(j);
			X[i].resize(G[i].size());
			dist[i].resize(G[i].size(), (1 << 30));
			for (int j = 0; j < (int)G[i].size() - 1; j++) {
				connect(i, j, i, j + 1);
				connect(i, j + 1, i, j);
				connect(i, j, 0, G[i][j + 1]);
				connect(i, j + 1, 0, G[i][j]);
			}
		}
		int pos1 = lower_bound(G[J].begin(), G[J].end(), A[i]) - G[J].begin();
		if (A[i] + P[i] < N) connect(0, A[i], 0, A[i] + P[i]);
		if (A[i] - P[i] >= 0) connect(0, A[i], 0, A[i] - P[i]);
		if (pos1 >= 1) connect(0, A[i], J, pos1 - 1);
		if (pos1 + 1 < G[J].size()) connect(0, A[i], J, pos1 + 1);
	}
	dist[0][0] = 0; Q.push(make_pair(0, 0));

	while (!Q.empty()) {
		int pos1 = Q.front().first, pos2 = Q.front().second; Q.pop();
		for (int i = 0; i < X[pos1][pos2].size(); i++) {
			int to1 = X[pos1][pos2][i].first, to2 = X[pos1][pos2][i].second;
			if (dist[to1][to2] > dist[pos1][pos2] + 1) {
				dist[to1][to2] = dist[pos1][pos2] + 1;
				Q.push(make_pair(to1, to2));
			}
		}
	}
	if (dist[0][1] == (1 << 30)) dist[0][1] = -1;
	cout << dist[0][1] << endl;
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pos1 + 1 < G[J].size()) connect(0, A[i], J, pos1 + 1);
       ~~~~~~~~~^~~~~~~~~~~~~
skyscraper.cpp:44:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < X[pos1][pos2].size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 3 ms 2424 KB Output is correct
3 Incorrect 3 ms 2456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2508 KB Output is correct
2 Correct 3 ms 2692 KB Output is correct
3 Incorrect 3 ms 2692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2692 KB Output is correct
2 Correct 3 ms 2692 KB Output is correct
3 Incorrect 3 ms 2692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2692 KB Output is correct
2 Correct 3 ms 2692 KB Output is correct
3 Incorrect 3 ms 2692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2692 KB Output is correct
2 Correct 3 ms 2692 KB Output is correct
3 Incorrect 4 ms 2692 KB Output isn't correct
4 Halted 0 ms 0 KB -