Submission #317732

#	Time	Username	Problem	Language	Result	Execution time	Memory
317732		MahdiBahramian	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	57 / 100	1042 ms	248844 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 = 95;
const int INF = 1000000010;

vector<int> pws[Max];
int dist[Max * (Sq + 1)];
bool que[Max * (Sq + 1)];
vector<pair<int, int> > N[Max * (Sq + 1)];
int n , m;

void DFS(int v)
{
	/*
	set<pair<int,int> > st;
	st.ins(mp(0 , v)); 
	dist[v] = 0;
	while(st.size())
	{
		v = st.begin()->S;
		st.erase(st.begin());
		for(var u : N[v])
		{
			if(dist[u.F] > dist[v] + u.S)
			{
				st.erase(mp(dist[u.F] , u.F));
				dist[u.F] = dist[v] + u.S;
				st.ins(mp(dist[u.F] , u.F));
			}
		}
	}
	*/

	srand(time(0));
	for(int i = 0; i < n * (Sq + 1) ; i++)
		random_shuffle(N[i].begin() , N[i].end());
	queue<int> q; q.push(v); dist[v] = 0; que[v] = true;
	while(q.size())
	{
		int v = q.front();
		q.pop();
		que[v] = false;
		for(var u : N[v])
		{
			if(dist[u.F] > dist[v] + u.S)
			{
				dist[u.F] = dist[v] + u.S;
				if(!que[u.F])
				{
					q.push(u.F);
					que[u.F] = true;
				}
			}
		}
	}
}
#define index(a , b) ((a) * (Sq+1) + b)
void connect(pii a , pii b , int d)
{
	//cout << "(" << a.F << "," << a.S << ") -> (" << b.F << "," << b.S << ")\n";
	//N[a.F][a.S].pb(mp(b , d));
	N[index(a.F , a.S)].pb(mp(index(b.F , b.S) , d));
}
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++)
	{
		dist[index(i , 0)] = INF;
		for(int j = 1; j <= Sq; j++)
		{
			dist[index(i , j)] = INF;
			if(i >= j)
			{
				connect(mp(i , j) , mp(i - j , j) , 1);
				connect(mp(i - j , j) , mp(i , j) , 1);
			}
			connect(mp(i , j) , mp(i , 0) , 0);
		}
		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)
				connect(mp(i , 0) , mp(i , x) , 0);
			else
			{
				for(int j = i - x , d = 1; j >= 0 ; j -= x , d++)
					connect(mp(i , 0) , mp(j , 0) , d);
				for(int j = i + x , d = 1; j < n ; j += x , d++)
					connect(mp(i , 0) , mp(j , 0) , d);
			}
		}
	}
	DFS(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: 0 / 43