Submission #582993

#	Time	Username	Problem	Language	Result	Execution time	Memory
582993		Justin1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	973 ms	262144 KiB

skyscraper

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

struct edge{
	int v, c;
};

const int maxpow = 2000;
const int dqsize = 4002005;

int n,m,k,x,y,z;
int pos[4002005], power[4002005];
vector<edge> gph[4002005];
int dis[4002005], inq[4002005];
int nxt[4002005], 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[f(pos[1],power[1])] = 0;
	push_back(f(pos[1],power[1]));
	inq[f(pos[1],power[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 >> pos[i] >> power[i];
	for (int i = 1; i <= m; i++) pos[i]++;
	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});
	}
	for (int i = 1; i <= m; i++) gph[n*maxpow+pos[i]].push_back({f(pos[i],power[i]),0});
	spfa();
}

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