Submission #123571

#	Time	Username	Problem	Language	Result	Execution time	Memory
123571		egorlifar	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	461 ms	112632 KiB

skyscraper

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";
const int MAXN = 30228;


int n, m;
int b[MAXN];
int p[MAXN];
vector<int> kek[MAXN];
queue<pair<pair<int, int>, int> > q;
bitset<30001> was[30001];


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> b[i] >> p[i];
	}
	for (int i = 0; i < m; i++) {
		kek[b[i]].pb(p[i]);
	}
	if (b[1] == b[0]) {
		cout << 0 << '\n';
		return 0;
	}
	for (int i = 0; i < n; i++) {
		sort(all(kek[i]));
		kek[i].resize(distance(kek[i].begin(), unique(all(kek[i]))));
	}
	for (auto x: kek[b[0]]) {
		q.push({{b[0], x}, 0});
		was[b[0]][x] = true;
	}
	while (!q.empty()) {
		auto x = q.front();
		q.pop();
		int pos = x.first.first;
		int jump = x.first.second;
		int cnt = x.second;
		for (int f = pos - jump; f <= pos + jump; f += 2 * jump) {
			if (f >= 0 && f < n) {
				if (!was[f][jump]) {
					was[f][jump] = true;
					if (f == b[1]) {
						cout << cnt + 1 << endl;
						exit(0);
					}
					q.push({{f, jump}, cnt + 1});
				}
				for (auto y: kek[f]) {
					if (!was[f][y]) {
						was[f][y] = true;
						q.push({{f, y}, cnt + 1});
					}
				}		
				kek[f].clear();
			}
		}

	}
	cout << -1 << endl;
	return 0;
}

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