Submission #531148

#	Time	Username	Problem	Language	Result	Execution time	Memory
531148		Hanksburger	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1094 ms	242736 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
int deq[21000005], edge[21000005], nxt[21000005], lnk[10500005], dist[10500005], a[30005][175], n, m, s, t, sz, cnt, l=10500000, r=10500000;
void add(int u, int v, int w)
{
	cnt++;
	edge[cnt]=v*2+w;
	nxt[cnt]=lnk[u];
	lnk[u]=cnt;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	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++;
				add(a[b%p][p], b%p, 0);
				for (int j=b%p+p; j<n; j+=p)
				{
					a[j][p]=sz;
					sz++;
					add(a[j][p], j, 0);
					add(a[j][p], a[j-p][p], 1);
					add(a[j-p][p], a[j][p], 1);
				}
			}
			add(b, a[b][p], 0);
		}
		else
		{
			int prev=b;
			for (int j=b-p; j>=0; j-=p)
			{
				add(prev, sz, 1);
				add(sz, j, 0);
				prev=sz;
				sz++;
			}
			prev=b;
			for (int j=b+p; j<n; j+=p)
			{
				add(prev, sz, 1);
				add(sz, j, 0);
				prev=sz;
				sz++;
			}
		}
	}
	for (int i=0; i<sz; i++)
		dist[i]=1e9;
	dist[s]=0;
	deq[10500000]=s;
	while (l<=r)
	{
		int u=deq[l], cur;
		l++;
		cur=lnk[u];
		while (cur)
		{
			int v=edge[cur]>>1, w=edge[cur]&1;
			if (dist[v]==1e9)
			{
				dist[v]=dist[u]+w;
				if (w)
				{
					r++;
					deq[r]=v;
				}
				else
				{
					l--;
					deq[l]=v;
				}
			}
			cur=nxt[cur];
		}
	}
	if (dist[t]==1e9)
		cout << -1;
	else
		cout << dist[t];
	return 0;
}

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