Submission #537210

#	Time	Username	Problem	Language	Result	Execution time	Memory
537210		Gurban	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	448 ms	262144 KiB

skyscraper

#include "bits/stdc++.h"
using namespace std;

using ll = long long;

const int maxn=3e4+5;
const int B = 140;
int n,m;
int b[maxn],p[maxn];
int ver[maxn][B];
int dis[maxn * B];
bool vis[maxn * B];
vector<pair<int,int>>E[maxn * B];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	int sq = min((int)sqrt(n),139);
	int sz = n - 1;
	for(int i = 0;i < n;i++) for(int j = 1;j <= sq;j++) ver[i][j] = ++sz;
	for(int i = 0;i < n;i++){
		for(int j = 1;j <= sq;j++){
			E[ver[i][j]].push_back({i,0});
			// E[i].push_back({ver[i][j],0});
			if(i - j >= 0) E[ver[i][j]].push_back({ver[i-j][j],1});
			if(i + j < n) E[ver[i][j]].push_back({ver[i+j][j],1});
		}
	}
	for(int i = 0;i < m;i++){
		cin >> b[i] >> p[i];
		if(p[i] <= sq){
			E[b[i]].push_back({ver[b[i]][p[i]],0});
			E[ver[b[i]][p[i]]].push_back({b[i],0});
		}
		else {
			for(int j = 1;b[i] - j * p[i] >= 0;j++) E[b[i]].push_back({b[i] - j * p[i],j});
			for(int j = 1;b[i] + j * p[i] < n;j++) E[b[i]].push_back({b[i] + j * p[i],j});
		}
	}

	// cout<<E[22][0].first<<' '<<E[22][0].second<<'\n';

	for(int i = 0;i <= sz;i++) dis[i] = 1e9;
	dis[b[0]] = 0;
	priority_queue<pair<int,int>>q;
	q.push({0,b[0]});
	while(!q.empty()){
		int x = q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		// cout<<x<<'\n';
		for(auto i : E[x]){
			if(dis[i.first] > dis[x] + i.second){
				dis[i.first] = dis[x] + i.second;
				q.push({-dis[i.first],i.first});
			}
		}
	}
	if(dis[b[1]] == 1e9) cout<<-1;
	else cout<<dis[b[1]];
}

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