Submission #405425

#	Time	Username	Problem	Language	Result	Execution time	Memory
405425		yoavL	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1095 ms	1004 KiB

skyscraper

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

#define upmax(a, b) a = max(a, b);
#define upmin(a, b) a = min(a, b);
#define pr(x) cout << x << endl;
#define wpr(x) cout << #x << ": " << x << endl;
#define rep(i, s, e) for(ll i = s; i < e; i++)
#define rep(i, e) for(ll i = 0; i < e; i++)

using namespace std;

using ll = unsigned short int;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;


const ll inf = 5e4;
const ll maxn = 2002;
const ll maxm = 30002;


ll n, m;
vll have[maxn]; // [place][sky ind]
ll d[maxn][maxm];
ll s[maxm], p[maxm];
bool vis[maxn];
vll arr;

queue<pll> q; // {place, sky ind}

/*


I did:
d[place][ind] = min time for ind'th skycraper to reach place.
Graph size: n*m
I did BFS 01 for:
O(n*m)

We can also do:
d[ind] min time for ind'th skycraper to hear the news.
Then, dijkstra.

*/
inline void make(ll b, ll ind)
{
	ll jump = p[ind];
	if (b - jump >= 0 && d[b - jump][ind] == inf) {
		d[b - jump][ind] = d[b][ind] + 1;
		q.push({ b - jump, ind });
	}
	if (b + jump < n && d[b + jump][ind] == inf) {
		d[b + jump][ind] = d[b][ind] + 1;
		q.push({ b + jump, ind });
	}
}

inline void bfs()
{
	q.push({ s[0], 0 });
	d[s[0]][0] = 0;
	while (!q.empty()) {
		ll b = q.front().first;
		ll ind = q.front().second;

		q.pop();
		if (!vis[b]) {
			rep(i, have[b].size()) {
				if (d[b][have[b][i]] == inf) d[b][have[b][i]] = d[b][ind];
				else continue;
				make(b, have[b][i]);
			}
			vis[b] = true;
		}
		make(b, ind);
	}
}


ll dijkstra()
{
	priority_queue<pll, vpll, greater<pll>> pq;
	vll dist(m, inf);
	dist[0] = 0;
	pq.push({ 0, 0 });
	while (!pq.empty())
	{
		ll cur = pq.top().second;
		ll curdist = pq.top().first;
		pq.pop();
		for (ll i = 0; i < m; i++) {
			if (i == cur) continue;
			if (abs(s[cur] - s[i]) % p[cur] != 0) continue;
			ll w = abs(s[cur] - s[i]) / p[cur];
			if (dist[i] > curdist + w) {
				dist[i] = curdist + w;
				pq.push({ dist[i], i });
			}
		}
	}
	return dist[1];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	rep(i, m) {
		cin >> s[i] >> p[i];
		have[s[i]].push_back(i);
	}
	/*
	for (ll i = 0; i < n; i++) {
		vis[i] = false;
		for (ll j = 0; j < m; j++) {
			d[i][j] = inf;
		}
	}
	bfs();
	ll ans = d[s[1]][1];
	*/
	ll ans = dijkstra();
	if (ans == inf) {
		pr("-1");
	}
	else pr(ans);
}

/*
		//wpr(b);
		//wpr(ind);
		//cout << "dist: " << d[b][ind] << endl;
5 3
0 2
1 1
4 1


*/

Compilation message (stderr)

skyscraper.cpp:12: warning: "rep" redefined
   12 | #define rep(i, e) for(ll i = 0; i < e; i++)
      | 
skyscraper.cpp:11: note: this is the location of the previous definition
   11 | #define rep(i, s, e) for(ll i = s; i < e; i++)
      |

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