Submission #317799

#	Time	Username	Problem	Language	Result	Execution time	Memory
317799		MahdiBahramian	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	684 ms	51452 KiB

skyscraper

#include<bits/stdc++.h>
#define pb push_back
#define ins insert
#define F first
#define S second
#define var auto
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Max = 30002;
const int Sq = 200;
const int SQ = 2*Sq+1;
const int INF = 1000000010;

vector<int> pws[Max];
vector<int> t2[Max];
vector<int> t1[Max];
int dist[Max * SQ];
int n , m;

#define index(a , b) ((a)*SQ + (b))
void Find(int v)
{
	deque<int> q;q.pb(v);dist[v] = 0;
	while(q.size())
	{
		v = q.front();
		q.pop_front();
		int x = v / SQ;
		int y = v - x * SQ;
		//if(y <= Sq)
		//	cout << "(" << x << "," << y << ") = " << dist[v] << "\n";
		if(y == 0)
		{
			//yal haye 0
			for(int z : t1[x])
			{
				if(dist[index(x , z)] > dist[v])
				{
					dist[index(x , z)] = dist[v];
					q.push_front(index(x , z));
				}
			}
			//yal haye 1
			if(dist[index(x , Sq+1)] > dist[v] + 1)
			{
				dist[index(x , Sq+1)] = dist[v] + 1;
				q.pb(index(x , Sq+1));
			}
		}
		else if(y <= Sq)
		{
			//yal haye 0
			if(dist[index(x , 0)] > dist[v])
			{
				dist[index(x , 0)] = dist[v];
				q.push_front(index(x , 0));
			}
			//yal haye 1
			if(x + y < n)
				if(dist[index(x + y , y)] > dist[v] + 1)
				{
					dist[index(x + y , y)] = dist[v] + 1;
					q.pb(index(x + y , y));
				}
			if(x - y >= 0)
				if(dist[index(x - y , y)] > dist[v] + 1)
				{
					dist[index(x - y , y)] = dist[v] + 1;
					q.pb(index(x - y , y));
				}
		}
		else
		{
			
			y -= Sq; 
			//yal haye 0
			for(int z : t2[x])
			{
				if(x + y * z >= n)
					break;
				if(dist[index(x + y * z, 0)] > dist[v])
				{
					dist[index(x + y * z , 0)] = dist[v];
					q.push_front(index(x + y * z , 0));
				}
			}
			for(int z : t2[x])
			{
				if(x - y * z < 0)
					break;
				if(dist[index(x - y * z, 0)] > dist[v])
				{
					dist[index(x - y * z , 0)] = dist[v];
					q.push_front(index(x - y * z , 0));
				}
			}
			//yal haye 1
			if(y != Sq)
				if(dist[v + 1] > dist[v] + 1)
				{
					dist[v + 1] = dist[v] + 1;
					q.pb(v + 1);
				}
			
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int b0 = -1;
	int b1 = -1;
	for(int i = 0; i < m ; i++)
	{
		int b , p;cin >> b >> p;
		pws[b].pb(p);
		if(i == 0)
			b0 = b;
		if(i == 1)
			b1 = b;
	}

	for(int i = 0; i < n ; i++)
	{
		for(int j = 0; j < SQ; j++)
			dist[index(i , j)] = INF;
		sort(pws[i].begin() , pws[i].end());
		pws[i].resize(unique(pws[i].begin() , pws[i].end()) - pws[i].begin());

		for(int x : pws[i])
		{
			if(x <= Sq)
				t1[i].pb(x);
			else
				t2[i].pb(x);
		}
	}

	Find(index(b0 , 0));
	if(dist[index(b1 , 0)] < INF)
		cout << dist[index(b1 , 0)] << '\n';
	else
		cout << -1 << '\n';
}

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