Submission #241380

#	Time	Username	Problem	Language	Result	Execution time	Memory
241380		Berted	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1100 ms	118432 KiB

skyscraper

#include <iostream>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#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] = {};
vector<map<int, int>> adj;
vector<set<int>> edgeQuery;
priority_queue<pii, vector<pii>, greater<pii>> pq;

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++) 
	{
		adj.pub(map<int, int>()); 
		edgeQuery.pub(set<int>());
		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;
	}
	vi temp;
	for (int i = 0; i < n; i++)
	{
		// cout << i << "\n";
		while (edgeQuery[i].size())
		{
			int x = *edgeQuery[i].begin(), s = i % x, lst = -1, cnt = 0;
			//cout << " - " << i << " " << x << "\n";
			for (; s < n; s += x)
			{
				if (edgeQuery[s].count(x))
				{
					edgeQuery[s].erase(x);
					if (lst >= 0)
					{
						//cout << "CON " << lst << " " << s << "\n";
						if (adj[lst].count(s)) adj[lst][s] = min(adj[lst][s], cnt);
						else adj[lst][s] = cnt;
						//cout << "CON " << s << " " << lst << "\n";
						if (adj[s].count(lst)) adj[s][lst] = min(adj[s][lst], cnt);
						else adj[s][lst] = cnt;
					}
					lst = s; cnt = 1;
					for (int i = (int)temp.size() - 1; i >= 0; i--)
					{
						//cout << "CON " << s << " " << temp[i] << "\n";
						if (adj[s].count(temp[i])) adj[s][temp[i]] = min(adj[s][temp[i]], cnt);
						else {adj[s][temp[i]] = cnt;}
						cnt++;
					}
					temp.clear();
					cnt = 0;
				}
				else
				{
					if (lst >= 0) 
					{
						//cout << "CON " << lst << " " << s << "\n";
						if (adj[lst].count(s)) adj[lst][s] = min(adj[lst][s], cnt);
						else adj[lst][s] = cnt;
					}
					temp.push_back(s);
				}
				cnt++;
			}
			temp.clear();
		}
	}
	/*
	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: 0 / 43