oj.uz

Submission #745314

# Submission time Handle Problem Language Result Execution time Memory
745314 2023-05-19T20:24:29 Z IBory Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 109 ms 262144 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 9999999;
unordered_map<int, int> mv[33333];
vector<int> G[MAX];
int D[MAX];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, S, E;
	cin >> N >> M;
	map<pii, vector<int>> make;
	for (int i = 0; i < M; ++i) {
		int b, p;
		cin >> b >> p;
		if (i == 0) S = b;
		if (i == 1) E = b;
		make[{p, b % p}].push_back(b);
	}
	int node = N;

	for (auto& [q, v] : make) {
		auto [p, i] = q;
		vector<int> fr;
		for (int j = i; j < N; j += p) fr.push_back(j);
		int base = -1;
		for (int n = 0; n < fr.size(); ++n) {
			G[node].push_back(fr[n]);
			if (base != -1) G[base].push_back(node);
			base = node++;
		}
		base = -1;
		for (int n = fr.size() - 1; n >= 0; --n) {
			G[node].push_back(fr[n]);
			if (base != -1) G[base].push_back(node);
			base = node++;
		}
		for (int s : v) {
			int n = (s - i) / p;
			if (n) G[s].push_back(fr[n - 1]);
			if (n + 1 < fr.size()) G[s].push_back(fr[n + 1]);
			if (1 < n) G[s].push_back(node - (n - 1));
			if (n + 2 < fr.size()) G[s].push_back(node - 2 * fr.size() + n + 2);
		}
	}

	memset(D, 0x3f, sizeof(D));
	D[S] = 0;
	queue<int> Q;
	Q.push(S);
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();
		for (int next : G[cur]) {
			if (D[next] < 1e9) continue;
			D[next] = D[cur] + 1;
			Q.push(next);
		}
	}

	cout << (D[E] > 1E9 ? -1 : D[E]);
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:24:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |  for (auto& [q, v] : make) {
      |             ^
skyscraper.cpp:25:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |   auto [p, i] = q;
      |        ^
skyscraper.cpp:29:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (int n = 0; n < fr.size(); ++n) {
      |                   ~~^~~~~~~~~~~
skyscraper.cpp:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if (n + 1 < fr.size()) G[s].push_back(fr[n + 1]);
      |        ~~~~~~^~~~~~~~~~~
skyscraper.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    if (n + 2 < fr.size()) G[s].push_back(node - 2 * fr.size() + n + 2);
      |        ~~~~~~^~~~~~~~~~~
skyscraper.cpp:62:14: warning: 'E' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  cout << (D[E] > 1E9 ? -1 : D[E]);
      |           ~~~^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 105 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 107 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 109 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -