제출 #1179185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179185		alexander707070	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	148 ms	71476 KiB

skyscraper

#include<bits/stdc++.h>
#define MAXN 30007
using namespace std;

struct doge{
	int pos,jump;

	inline friend bool operator < (doge fr,doge sc){
		if(fr.jump!=sc.jump)return fr.jump<sc.jump;
		if(fr.pos%fr.jump!=sc.pos%sc.jump)return fr.pos%fr.jump<sc.pos%sc.jump;
		return fr.pos<sc.pos;
	}
}d[MAXN];

int n,m,dist[MAXN];
vector<doge> w;

vector< pair<int,int> > v[MAXN];
priority_queue < pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > > q;
bool vis[MAXN];

void add_edge(int x,int y,int z){
	v[x].push_back({y,z});
}

void dijkstra(int x){
	for(int i=0;i<n;i++)dist[i]=n*n;

	dist[x]=0;
	q.push({0,x});

	while(!q.empty()){
		int minv=q.top().second;
		q.pop();

		if(vis[minv])continue;
		vis[minv]=true;

		for(auto nxt:v[minv]){
			if(vis[nxt.first] or dist[nxt.first]<=dist[minv]+nxt.second)continue;

			dist[nxt.first]=dist[minv]+nxt.second;
			q.push({dist[nxt.first],nxt.first});
		}
	}
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>m;

	for(int i=1;i<=m;i++){
		cin>>d[i].pos>>d[i].jump;
	}

	int st=d[1].pos;
	int et=d[2].pos;

	sort(d+1,d+m+1);

	for(int i=1;i<=m;i++){
		if(i<m and d[i].jump==d[i+1].jump and d[i].pos%d[i].jump==d[i+1].pos%d[i+1].jump){
			w.push_back(d[i]);
			continue;
		}

		w.push_back(d[i]);
		for(int i=0;i<w.size();i++){
			for(int t=1;(i==0 or w[i].pos-t*w[i].jump>=w[i-1].pos) and w[i].pos-t*w[i].jump>=0;t++){
				add_edge(w[i].pos,w[i].pos-t*w[i].jump,t);
			}

			for(int t=1;(i==w.size()-1 or w[i].pos+t*w[i].jump<=w[i+1].pos) and w[i].pos+t*w[i].jump<n;t++){
				add_edge(w[i].pos,w[i].pos+t*w[i].jump,t);
			}
		}

		w.clear();
	}

	dijkstra(st);

	if(!vis[et]){
		cout<<"-1\n";
	}else{
		cout<<dist[et]<<"\n";
	}

	return 0;
}

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