Submission #583182

#	Time	Username	Problem	Language	Result	Execution time	Memory
583182		Justin1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	201 ms	201108 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
struct edge{
	int v, c;
};
 
const int maxpow = 1;
const int dqsize = 5500000;
 
int n,m,k,x,y,z;
int pos[3], power[3];
vector<edge> gph[5500000];
int dis[5500000];
vector<bool> inq(5500000);
int nxt[5500000], head, tail;
 
int f(int i, int j) { //2d to 1d
	return (i-1)*maxpow+j;
}
 
bool empty() {
	return head == tail;
}
 
void push_back(int x) {
	nxt[tail] = x;
	tail = (tail+1) % dqsize;
}
 
void push_front(int x) {
	head = (head-1+dqsize) % dqsize;
	nxt[head] = x;
}
 
int front() {
	return nxt[head];
}
 
int back() {
	return nxt[(tail-1+dqsize) % dqsize];
}
 
void pop_front() {
	head = (head+1) % dqsize;
}
 
void pop_back() {
	tail = (tail-1+dqsize) % dqsize;
}
 
void spfa() {
	for (int i = 1; i <= n*maxpow+n; i++) dis[i] = 1e9;
	dis[n*maxpow+pos[1]] = 0;
	push_back(n*maxpow+pos[1]);
	inq[n*maxpow+pos[1]] = 1;
	while (!empty()) {
		auto tmp = front();
		pop_front();
		inq[tmp] = 0;
		for (auto i : gph[tmp]) {
			if (dis[tmp] + i.c < dis[i.v]) {
				dis[i.v] = dis[tmp] + i.c;
				if (!inq[i.v]) push_back(i.v);
				inq[i.v] = 1;
				if (dis[back()] < dis[front()]){
					push_front(back());
					pop_back();
				}
			}
		}
	}
	if (dis[n*maxpow+pos[2]] == 1e9) cout << "-1\n";
	else cout << dis[n*maxpow+pos[2]] << '\n';
}
 
int main() {
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		x++;
		if (y > maxpow) {
			for (int j = x - y, c = 1; j >= 1; j -= y, c++) 
				gph[n*maxpow+x].push_back({n*maxpow+j,c});
			for (int j = x + y, c = 1; j <= n; j += y, c++) 
				gph[n*maxpow+x].push_back({n*maxpow+j,c});
		} else {
			gph[n*maxpow+x].push_back({f(x,y),0});
		}
		if (i <= 2) pos[i] = x, power[i] = y;
	}
	for (int i = 1; i <= maxpow; i++) { //pow
		for (int j = 1; j <= i; j++) {
			for (int l = j; l+i <= n; l += i) { //pos
				gph[f(l,i)].push_back({f(l+i,i),1});
				gph[f(l+i,i)].push_back({f(l,i),1});
			}
		}
		for (int j = 1; j <= n; j++) gph[f(j,i)].push_back({n*maxpow+j,0});
	}
	spfa();
}

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