Submission #241407

#	Time	Username	Problem	Language	Result	Execution time	Memory
241407		Berted	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	217 ms	65516 KiB

skyscraper

#include <iostream>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define pii pair<int, int>
#define fst first
#define snd second
#define vi vector<int>
#define vpi vector<pii>
#define pub push_back
using namespace std;

const int MX = 1e9;

int n, m, s, e, dst[30001] = {};
vpi adj[30001];
unordered_set<int> edgeQuery[30001];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int temp[30001] = {}, tpsz = 0;

inline int dijkstra()
{
	pq.push({0, s});
	dst[s] = 0;
	while (pq.size())
	{
		pii dt = pq.top(); pq.pop();
		if (dst[dt.snd] == dt.fst)
		{
			//cout << "DIK : " << dt.snd << ", " << dt.fst << "\n";
			if (dt.snd == e) {return dt.fst;}
			for (auto v : adj[dt.snd])
			{
				if (dt.fst + v.snd < dst[v.fst])
				{
					dst[v.fst] = dt.fst + v.snd;
					pq.push({dt.fst + v.snd, v.fst});
				}
			}
		}
	}
	return -1;
}

int main()
{
	// ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
	{
		dst[i] = MX;
	}
	for (int i = 0; i < m; i++)
	{
		int u, t; cin >> u >> t;
		edgeQuery[u].insert(t);
		if (i == 0) s = u;
		else if (i == 1) e = u;
	}
	
	for (int i = 0; i < n; i++)
	{
		while (edgeQuery[i].size())
		{
			int x = *edgeQuery[i].begin(), s = i % x, lst = -1, cnt = 0;
			for (; s < n; s += x)
			{
				if (edgeQuery[s].count(x))
				{
					edgeQuery[s].erase(x);
					if (lst >= 0)
					{
						adj[lst].push_back({s, cnt});
						adj[s].push_back({lst, cnt});
					}
					lst = s; cnt = 1;
					for (int i = tpsz - 1; i >= 0; i--)
					{
						adj[s].push_back({temp[i], cnt});
						cnt++;
					}
					tpsz = 0;
					cnt = 0;
				}
				else
				{
					if (lst >= 0) 
					{
						adj[lst].push_back({s, cnt});
					}
					temp[tpsz++] = s;
				}
				cnt++;
			}
			tpsz = 0;
		}
	}

	/*
	for (int i = 0; i < n; i++)
	{
		cout << i << "-th node adjacency list :\n";
		for (auto x : adj[i])
		{
			cout << x.fst << ", " << x.snd << '\n';
		}
	}
	cout << "Here\n";
	*/
	
	cout << dijkstra() << '\n';
	return 0;
}

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