제출 #679780

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

skyscraper

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e4 + 10 , maxsq = 150 , inf = 1e9 + 10;
int n , b[maxn] , p[maxn] , m , dis[maxn][maxsq + 10] , ans;
bool marked[maxn];
vector <int> all[maxn];
set <pair <int , pair <int , int>>> st;

void add(int v , int j , int val)
{
	if(dis[v][j] > val)
	{
		st.erase({dis[v][j] , {v , j}});
		dis[v][j] = val;
		st.insert({dis[v][j] , {v , j}});
	}
}

void jmp_small(int D , int now , int jmp)
{
	if(now + jmp < n)
		add(now + jmp , jmp , D + 1);
	if(now - jmp > -1)
		add(now - jmp , jmp , D + 1);
}

void jmp_big(int D , int now , int jmp)
{
	for(int tmp = now + jmp ; tmp < n ; tmp += jmp)
		add(tmp , maxsq , D + ((tmp - now) / jmp));
	for(int tmp = now - jmp ; tmp > -1 ; tmp -= jmp)
		add(tmp , maxsq , D + ((now - tmp) / jmp));
}

void update(int D , int now , int jmp)
{
	if(jmp != maxsq)
	{
		jmp_small(D , now , jmp);
		return;
	}
	if(marked[now])
		return;
	marked[now] = true;
	for(auto u : all[now])
	{
		if(u < maxsq)
			jmp_small(D , now , u);
		else
			jmp_big(D , now , u);
	}
}

void dij()
{
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j <= maxsq ; j++)
			dis[i][j] = inf;
	dis[b[0]][maxsq] = 0;
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j <= maxsq ; j++)
			st.insert({dis[i][j] , {i , j}});
	while(!st.empty())
	{
		auto v = *st.begin();
		st.erase(v);
		int D = v.F , now = v.S.F , jmp = v.S.S;
		if(now == b[1])
		{
			ans = D;
			break;
		}
		if(!marked[now])
		{
			jmp = maxsq;
			update(D , now , jmp);
		}
		jmp = v.S.S;
		update(D , now , jmp);
	}
}	

int32_t main()
{
	fast;
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++)
	{
		cin >> b[i] >> p[i];
		all[b[i]].pb(p[i]);
	}
	dij();
	cout << (ans == inf ? -1 : ans) << endl;
	return 0;
}

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