제출 #110242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110242		hugo_pm	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1054 ms	77384 KiB

skyscraper

#pragma GCC optimize("O3")
#pragma GCC target("sse2,sse3,ssse3,sse4,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
 
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
 
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
 
const int BIG = 2*(int)(1e9);
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
 
void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}
 
const int borneSuj = 30*1000 + 5;
const int borneTab = 200*borneSuj;
int gt[borneSuj][200];
int inv[borneTab];
bool witPrev[borneTab];
bool witSuiv[borneTab];
 
int arr = -1, dep=-1;
 
int nbPlaces, nbDoges, nbNoeuds;
int limSqd;
 
vector<int> doge[borneSuj];
 
bool dfs()
{
	vector<int> st;
	vector<bool> vu(nbNoeuds, false);

	st.push_back(dep); vu[dep] = true;
	while (!st.empty()) {
		int nod = st.back(); st.pop_back();
		if (nod == arr) return true;
		if (nod < nbPlaces) {
			int pos = nod;
			for (int saut : doge[nod]) {
				if (saut < limSqd) {
					int kk = gt[pos][saut];
					if (!vu[kk]) { st.push_back(kk); vu[kk] = true; }
				} else {
					for (int dd = 1; pos + dd*saut < nbPlaces; ++dd) {
						if (!vu[pos+dd*saut]) { st.push_back(pos+dd*saut); vu[pos+dd*saut] = true; }
					}
		 
					for (int dd = 1; pos - dd*saut >= 0; ++dd) {
						if (!vu[pos-dd*saut]) { st.push_back(pos-dd*saut); vu[pos-dd*saut] = true; }
					}
				}
			}
		} else {
			if (inv[nod] && !vu[inv[nod]-1]) { st.push_back(inv[nod]-1); vu[inv[nod]-1] = true; }
			if (witPrev[nod] && !vu[nod-1]) { st.push_back(nod-1); vu[nod-1] = true; }
			if (witSuiv[nod] && !vu[nod+1]) { st.push_back(nod+1); vu[nod+1] = true; }
		}
	}
	return false;
}

void solve()
{
	cin >> nbPlaces >> nbDoges;
	chmax(nbPlaces, 20);
	nbNoeuds = nbPlaces;
	limSqd = sqrt(nbPlaces);
 
	form2(distance, 1, limSqd) {
		form(ini, distance) {
			for (int place = ini; place < nbPlaces; place += distance) {
				int corNod = nbNoeuds; ++nbNoeuds;
				inv[corNod] = place+1;
				gt[place][distance] = corNod;
 
				if (place != ini) {
					witPrev[corNod] = true;
					witSuiv[corNod-1] = true;
				}
			}
		}
	}
 
	form(iDoge, nbDoges) {
		int pos, saut;
		cin >> pos >> saut;
		if (iDoge == 0) dep = pos;
		if (iDoge == 1) arr = pos;
		doge[pos].push_back(saut);
	}
	
	if (!dfs()) { cout << "-1\n"; return; }

	vector<int> md(nbNoeuds, BIG);
	md[dep] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0,dep});
	while (! pq.empty()) {
		int dis = pq.top().fi, nod = pq.top().se;
		pq.pop();
		if (nod == arr) { cout << dis << "\n"; return; }
		if (dis != md[nod]) continue;
 
 		auto propag = [&] (int vo, int poids) {
			if (dis + poids < md[vo]) {
				md[vo] = dis+poids;
				pq.push({md[vo], vo});
			}
		};
 
		if (nod < nbPlaces) {
			int pos = nod;
			for (int saut : doge[nod]) {
				if (saut < limSqd) {
					propag(gt[pos][saut], 0);
				} else {
					for (int dd = 1; pos + dd*saut < nbPlaces; ++dd) {
						propag(pos+dd*saut, dd);
					}
		 
					for (int dd = 1; pos - dd*saut >= 0; ++dd) {
						propag(pos-dd*saut, dd);
					}
				}
			}
		}
 
		if (nod >= nbPlaces) {
			if (inv[nod]) propag(inv[nod]-1, 0);
			if (witPrev[nod]) propag(nod-1, 1);
			if (witSuiv[nod]) propag(nod+1, 1);
		}
	}
 
	cout << md[arr] << "\n";
}

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