제출 #531151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531151		Hanksburger	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1108 ms	243628 KiB

skyscraper

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