oj.uz

Submission #771260

# Submission time Handle Problem Language Result Execution time Memory
771260 2023-07-02T18:23:28 Z IBory Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 74 ms 153176 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 5555555;
vector<int> G[MAX];
vector<int> C[30003];
bitset<MAX> noL, noR;
int D[MAX];

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

	int node = N + 1, SN, EN;
	for (auto& [q, v] : make) {
		auto [p, i] = q;
		if (!i) i += p;
		vector<int> fr;
		for (int j = i; j <= N; j += p) {
			if (S == pii{ j, p }) SN = node;
			if (E == pii{ j, p }) EN = node;
			C[j].push_back(node);
			fr.push_back(node++);
		}
		noL[fr[0]] = noR[fr.back()] = 1;
		for (int n : v) {
			G[n].push_back(-fr[(n - 1) / p]);
		}
	}
	make.clear();
	
	for (int i = 1; i <= N; ++i) {
		for (int n : C[i]) {
			G[n].push_back(-i);
		}
		C[i].clear();
	}

	memset(D, 0x3f, sizeof(D));
	D[SN] = 0;
	deque<int> Q;
	Q.push_back(SN);
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop_front();
		if (!noL[cur]) G[cur].push_back(cur - 1);
		if (!noR[cur]) G[cur].push_back(cur + 1);

		for (int next : G[cur]) {
			int d = 1;
			if (next < 0) {
				d = 0;
				next *= -1;
			}
			if (D[cur] + d >= D[next]) continue;
			D[next] = D[cur] + d;
			if (d == 0) Q.push_front(next);
			else Q.push_back(next);
		}

		if (!noL[cur]) G[cur].pop_back();
		if (!noR[cur]) G[cur].pop_back();
	}

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

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:30:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |  for (auto& [q, v] : make) {
      |             ^
skyscraper.cpp:31:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   auto [p, i] = q;
      |        ^
skyscraper.cpp:79:15: warning: 'EN' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |  cout << (D[EN] > 1E9 ? -1 : D[EN]);
      |           ~~~~^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 153112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 153108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 153176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 153164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 153108 KB Output isn't correct
2 Halted 0 ms 0 KB -