Submission #531132

#	Time	Username	Problem	Language	Result	Execution time	Memory
531132		Hanksburger	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	147 ms	262148 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, bool> > adj[10500005];
int dist[10500005], a[30005][175];
deque<int> deq;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, s, t, sz;
	cin >> n >> m;
	sz=n;
	for (int i=0; i<m; i++)
	{
		int b, p;
		cin >> b >> p;
		if (i==0)
			s=b;
		else if (i==1)
			t=b;
		if (p*p<=m)
		{
			if (!a[b][p])
			{
				a[b%p][p]=sz;
				sz++;
				adj[a[b%p][p]].push_back({b%p, 0});
				for (int j=b%p+p; j<n; j+=p)
				{
					a[j][p]=sz;
					sz++;
					adj[a[j][p]].push_back({j, 0});
					adj[a[j][p]].push_back({a[j-p][p], 1});
					adj[a[j-p][p]].push_back({a[j][p], 1});
				}
			}
			adj[b].push_back({a[b][p], 0});
		}
		else
		{
			int prev=b;
			for (int j=b-p; j>=0; j-=p)
			{
				adj[prev].push_back({sz, 1});
				adj[sz].push_back({j, 0});
				prev=sz;
				sz++;
			}
			prev=b;
			for (int j=b+p; j<n; j+=p)
			{
				adj[prev].push_back({sz, 1});
				adj[sz].push_back({j, 0});
				prev=sz;
				sz++;
			}
		}
	}
	for (int i=0; i<sz; i++)
		dist[i]=1e9;
	dist[s]=0;
	deq.push_back(s);
	while (!deq.empty())
	{
		int u=deq.front();
		deq.pop_front();
		for (int i=0; i<adj[u].size(); i++)
		{
			int v=adj[u][i].first;
			bool w=adj[u][i].second;
			if (dist[v]==1e9)
			{
				dist[v]=dist[u]+w;
				if (w)
					deq.push_back(v);
				else
					deq.push_front(v);
			}
		}
	}
	if (dist[t]==1e9)
		cout << -1;
	else
		cout << dist[t];
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int i=0; i<adj[u].size(); i++)
      |                 ~^~~~~~~~~~~~~~
skyscraper.cpp:82:12: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |  if (dist[t]==1e9)
      |      ~~~~~~^

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