Submission #558809

#	Time	Username	Problem	Language	Result	Execution time	Memory
558809		hhhhaura	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	159 ms	150032 KiB

skyscraper

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
namespace solver {
	int n, m, s, t, ii;
	const int P = 180, mx = 1000000;
	vector<pii> mp[mx], a;
	vector<int> v[P + 1][P + 1];
	vector<int> dis;
	void init_(int _n, int _m) {
		ii = _n;
		n = _n, m = _m;
		a.clear();
		dis.assign(mx, INF);
	}
	void solve() {
		for(auto i : a) {
			int st = i.y % i.x;
			for(int j = st; j < n; j += i.x) {
				ii++;
				if(j != st) mp[ii].push_back({ii - 1, 1});
				if(j + i.x < n) mp[ii].push_back({ii + 1, 1});
				if(j == i.y) mp[j].push_back({ii, 0});
				mp[ii].push_back({j, 0});
			}
		}
		rep(i, 1, P) rep(j, 0, i - 1) {
			sort(all(v[i][j]));
			if(!v[i][j].size()) continue;
			int cur = 0;
			for(int k = j; k < n; k += i) {
				ii++;
				if(k != j) mp[ii].push_back({ii - 1, 1});
				if(k + i < n) mp[ii].push_back({ii + 1, 1});
				if(cur < v[i][j].size() && 
					v[i][j][cur] == k) mp[k].push_back({ii, 0}), cur++;
				mp[ii].push_back({k, 0});
			}
		}
		dis[s] = 0;
		deque<int> q;
		q.push_back(s);
		while(q.size()) {
			int cur = q.front();
			q.pop_front();
			if(cur == t) {
				cout << dis[cur] << "\n";
				return;
			}
			for(auto i : mp[cur]) {
				if(dis[i.x] != INF) continue;
				dis[i.x] = dis[cur] + i.y;
				if(i.y) q.push_back(i.x);
				else q.push_front(i.x);
			}
		}
		cout << "-1\n";
		return;

	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m;
	cin >> n >> m;
	init_(n, m);
	rep(i, 0, m - 1) {
		int b, p;
		cin >> b >> p;
		if(i == 0) s = b;
		if(i == 1) t = b;
		if(p <= P) v[p][b % p].push_back(b);
		else a.push_back({p, b});
	}
	solve();
	return 0;
}

Compilation message (stderr)

skyscraper.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
skyscraper.cpp:19:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
skyscraper.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~
skyscraper.cpp: In function 'void solver::solve()':
skyscraper.cpp:59:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     if(cur < v[i][j].size() &&
      |        ~~~~^~~~~~~~~~~~~~~~

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