Submission #1272038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272038		thuhienne	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1097 ms	23232 KiB

skyscraper

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

#define end __end__

const int can = 175;

int n,m,start,end;
vector <int> power[30009];

int l[30009][can + 3];

struct doges {
	int vertice,jump,cost;
	bool operator < (const doges & other) const {
		return cost > other.cost;
	}
};

void djt() {
	for (int i = 1;i <= n;i++) for (int j = 1;j <= can + 1;j++) l[i][j] = 1e9;
	l[start][can + 1] = 0;
	priority_queue <doges> pq;
	pq.push({start,can + 1,l[start][can + 1]});
	while (pq.size()) {
		int pos = pq.top().vertice,jump = pq.top().jump,cost = pq.top().cost;
		pq.pop();
		
		if (cost > l[pos][jump]) continue;
		
		if (pos == end) {
			cout << l[pos][jump];
			exit(0);
		}
		
		//TH1: Tiep tuc dung jump
		if (jump <= can) {
			if (pos - jump >= 1 && l[pos - jump][jump] > cost + 1) {
				l[pos - jump][jump] = cost + 1;
				pq.push({pos - jump,jump,l[pos - jump][jump]});
			}
			if (pos + jump <= n && l[pos + jump][jump] > cost + 1) {
				l[pos + jump][jump] = cost + 1;
				pq.push({pos + jump,jump,l[pos + jump][jump]});
			}
		}
		
		//TH2: Dung power khac
		for (auto pw : power[pos]) {
			if (pw > can) {
				for (int i = 1;pos - i * pw >= 1;i++) {
					if (l[pos - i * pw][can + 1] > cost + i) {
						l[pos - i * pw][can + 1] = cost + i;
						pq.push({pos - i * pw,can + 1,l[pos - i * pw][can + 1]});
					}
				}
				for (int i = 1;pos + i * pw <= n;i++) {
					if (l[pos + i * pw][can + 1] > cost + i) {
						l[pos + i * pw][can + 1] = cost + i;
						pq.push({pos + i * pw,can + 1,l[pos + i * pw][can + 1]});
					}
				}
			} else {
				if (l[pos][pw] > cost) {
					l[pos][pw] = cost;
					pq.push({pos,pw,l[pos][pw]});
				}
			}
		}	
	}
	cout << -1;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);
	cin >> n >> m;
	for (int i = 1;i <= m;i++) {
		int b,p;cin >> b >> p;
		b++;
		if (i == 1) start = b;
		if (i == 2) end = b;
		power[b].push_back(p);
	}
	djt();
}

/*
  Thuong em khi mua thu
  Thuong em sang mua ha
  Thuong em bang qua mua dong,gui gio xuan om em vao long
  Thuong em bao mua mua
  Tham thuong luon bao mua nang
  Thuong yeu em khong doi thay,gio mat em tim toi hao gay ):
*/

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