oj.uz

Submission #154691

# Submission time Handle Problem Language Result Execution time Memory
154691 2019-09-23T13:57:37 Z tinjyu Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 259 ms 190844 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 190648 KB Output is correct
2 Correct 171 ms 190584 KB Output is correct
3 Correct 169 ms 190636 KB Output is correct
4 Correct 173 ms 190700 KB Output is correct
5 Correct 168 ms 190552 KB Output is correct
6 Correct 167 ms 190556 KB Output is correct
7 Correct 169 ms 190580 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 190592 KB Output is correct
2 Correct 172 ms 190556 KB Output is correct
3 Correct 170 ms 190540 KB Output is correct
4 Correct 170 ms 190584 KB Output is correct
5 Correct 184 ms 190684 KB Output is correct
6 Correct 177 ms 190740 KB Output is correct
7 Correct 186 ms 190576 KB Output is correct
8 Correct 172 ms 190588 KB Output is correct
9 Correct 168 ms 190552 KB Output is correct
10 Correct 171 ms 190720 KB Output is correct
11 Correct 173 ms 190712 KB Output is correct
12 Incorrect 165 ms 190584 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 190584 KB Output is correct
2 Correct 259 ms 190592 KB Output is correct
3 Correct 185 ms 190624 KB Output is correct
4 Correct 217 ms 190660 KB Output is correct
5 Correct 175 ms 190632 KB Output is correct
6 Correct 199 ms 190712 KB Output is correct
7 Correct 186 ms 190712 KB Output is correct
8 Correct 170 ms 190584 KB Output is correct
9 Correct 170 ms 190712 KB Output is correct
10 Correct 173 ms 190636 KB Output is correct
11 Correct 171 ms 190732 KB Output is correct
12 Incorrect 171 ms 190624 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 190584 KB Output is correct
2 Correct 169 ms 190628 KB Output is correct
3 Correct 201 ms 190584 KB Output is correct
4 Correct 180 ms 190632 KB Output is correct
5 Correct 182 ms 190712 KB Output is correct
6 Correct 183 ms 190544 KB Output is correct
7 Correct 171 ms 190584 KB Output is correct
8 Correct 170 ms 190584 KB Output is correct
9 Correct 171 ms 190584 KB Output is correct
10 Correct 171 ms 190584 KB Output is correct
11 Correct 174 ms 190788 KB Output is correct
12 Incorrect 173 ms 190584 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 190556 KB Output is correct
2 Correct 167 ms 190556 KB Output is correct
3 Correct 170 ms 190584 KB Output is correct
4 Correct 168 ms 190584 KB Output is correct
5 Correct 170 ms 190612 KB Output is correct
6 Correct 169 ms 190584 KB Output is correct
7 Correct 168 ms 190508 KB Output is correct
8 Correct 180 ms 190588 KB Output is correct
9 Correct 169 ms 190584 KB Output is correct
10 Correct 169 ms 190584 KB Output is correct
11 Correct 171 ms 190844 KB Output is correct
12 Incorrect 172 ms 190656 KB Output isn't correct
13 Halted 0 ms 0 KB -