제출 #154691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154691		tinjyu	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	259 ms	190844 KiB

skyscraper

#include <iostream>
#include <cmath>
using namespace std;
long long int n,m,t[1000005][3],b[30005],p[30005],f[30005][405],ga[30005][405],road[30005],map[30005],tag[30005];
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)road[i]=-1;
	for(int i=0;i<m;i++)
	{
		cin>>b[i]>>p[i];
		map[i]=road[b[i]];
		road[b[i]]=i;
	}
	for(int i=0;i<30000;i++)
	{
		for(int j=0;j<400;j++)
		{
			f[i][j]=-1;
			ga[i][j]=-1;
		}
	}
	if(p[0]<=sqrt(n))
	{
		t[0][0]=b[0];
		t[0][1]=p[0];
		t[0][2]=2;
		ga[b[0]][p[0]]=0;
	}
	else
	{
		t[0][0]=0;
		t[0][1]=200;
		t[0][2]=1;
		f[0][200]=0;
	}
	tag[b[0]]=1;
	int g=road[b[0]];
	int pp=0,qq=0;
	while(g!=-1)
	{
		int now=g;
		if(now!=0)
		{
			qq++;
			if(p[now]<=sqrt(n) && ga[b[now]][p[now]]==-1)
			{
				
				t[qq][0]=b[now];
				t[qq][1]=p[now];
				t[qq][2]=2;
				ga[b[now]][p[now]]=0;
			}
			else
			{
				t[qq][0]=now;
				t[qq][1]=200;
				t[qq][2]=1;
				f[now][200]=0;
			}
		}
		g=map[g];
	}
	
	while(pp<=qq)
	{
		//cout<<"st "<<pp<<" "<<qq<<endl;
		//cout<<t[pp][0]<<" "<<t[pp][1]<<" "<<t[pp][2]<<endl;
		//if(t[pp][2]==1)cout<<f[t[pp][0]][t[pp][1]]<<endl;
		//else cout<<ga[t[pp][0]][t[pp][1]]<<endl;
		if(t[pp][2]==1)
		{
			int i=t[pp][0];
			int l=b[i]+(200-t[pp][1]-1)*p[i],r=b[i]+(200-t[pp][1]+1)*p[i];
			if(l>=0 && f[t[qq][0]][t[qq][1]]==-1)
			{
				qq++;
				t[qq][0]=t[pp][0];
				t[qq][1]=t[pp][1]-1;
				t[qq][2]=1;
				f[t[qq][0]][t[qq][1]]=f[t[pp][0]][t[pp][1]]+1;
			}
			if(l>=0 && tag[l]==0)
			{
				tag[l]=1;
				int g=road[l];
				while(g!=-1)
				{
					int now=g;
					qq++;
					//cout<<"ok"<<"1 "<<g<<" "<<l<<endl;
					if(p[now]<=sqrt(n) && ga[b[now]][p[now]]==-1)
					{
						t[qq][0]=b[now];
						t[qq][1]=p[now];
						t[qq][2]=2;
						ga[b[now]][p[now]]=f[t[pp][0]][t[pp][1]]+1;
					}
					else
					{
						t[qq][0]=now;
						t[qq][1]=200;
						t[qq][2]=1;
						f[now][200]=f[t[pp][0]][t[pp][1]]+1;
					}
					g=map[g];
				}
			}
			if(r<n && f[t[qq][0]][t[qq][1]]==-1)
			{
				qq++;
				t[qq][0]=t[pp][0];
				t[qq][1]=t[pp][1]+1;
				t[qq][2]=1;
				f[t[qq][0]][t[qq][1]]=f[t[pp][0]][t[pp][1]]+1;
				//cout<<"f"<<" "<<f[t[qq][0]][t[qq][1]]<<" "<<t[qq][0]<<" "<<t[qq][1]<<endl;
			}
			if(r<n && tag[r]==0)
			{
				tag[r]=1;
				int g=road[r];
				while(g!=-1)
				{
					int now=g;
					qq++;
					//cout<<"ok"<<"2 "<<g<<" "<<r<<endl;
					if(p[now]<=sqrt(n) && ga[b[now]][p[now]]==-1)
					{
						t[qq][0]=b[now];
						t[qq][1]=p[now];
						t[qq][2]=2;
						ga[b[now]][p[now]]=f[t[pp][0]][t[pp][1]]+1;
					}
					else
					{
						t[qq][0]=now;
						t[qq][1]=200;
						t[qq][2]=1;
						f[now][200]=f[t[pp][0]][t[pp][1]]+1;
					}
					g=map[g];
				}
			}
		}
		else
		{
			int l=t[pp][0]-t[pp][1],r=t[pp][0]+t[pp][1];
			if(l>=0 && ga[l][t[pp][1]]==-1)
			{
				qq++;
				t[qq][0]=l;
				t[qq][1]=t[pp][1];
				t[qq][2]=2;
				ga[l][t[pp][1]]=ga[t[pp][0]][t[pp][1]]+1;
			}
			if(l>=0 && tag[l]==0)
			{
				tag[l]=1;
				int g=road[l];
				while(g!=-1)
				{
					//cout<<"ok"<<"3 "<<g<<" "<<l<<endl;
					int now=g;
					qq++;
					if(p[now]<=sqrt(n) && ga[b[now]][p[now]]==-1)
					{
						t[qq][0]=b[now];
						t[qq][1]=p[now];
						t[qq][2]=2;
						ga[b[now]][p[now]]=ga[t[pp][0]][t[pp][1]]+1;
					}
					else
					{
						t[qq][0]=now;
						t[qq][1]=200;
						t[qq][2]=1;
						f[now][200]=ga[t[pp][0]][t[pp][1]]+1;
					}
					g=map[g];
				}
			}
			if(r<n && ga[r][t[pp][1]]==-1)
			{
				qq++;
				t[qq][0]=r;
				t[qq][1]=t[pp][1];
				t[qq][2]=2;
				ga[r][t[pp][1]]=ga[t[pp][0]][t[pp][1]]+1;
			}
			if(r<n && tag[r]==0)
			{
				tag[r]=1;
				int g=road[r];
				while(g!=-1)
				{
					//cout<<"ok"<<"4 "<<g<<" "<<r<<endl;
					int now=g;
					qq++;
					if(p[now]<=sqrt(n) && ga[b[now]][p[now]]==-1)
					{
						t[qq][0]=b[now];
						t[qq][1]=p[now];
						t[qq][2]=2;
						ga[b[now]][p[now]]=ga[t[pp][0]][t[pp][1]]+1;
					}
					else
					{
						t[qq][0]=now;
						t[qq][1]=200;
						t[qq][2]=1;
						f[now][200]=ga[t[pp][0]][t[pp][1]]+1;
					}
					g=map[g];
				}
			}
		}
		pp++;
	}
	long long int ans=999999999;
	for(int i=0;i<400;i++)
	{
		
		if(f[1][i]!=-1)ans=min(ans,f[1][i]);
	}
	for(int i=0;i<=300;i++)
	{
		if(ga[b[1]][i]!=-1)ans=min(ans,ga[b[1]][i]);
	}
	if(ans==999999999)cout<<"-1";
	else cout<<ans;
}

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