제출 #582974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582974		Justin1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	1032 ms	262144 KiB

skyscraper

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

struct edge{
	int v, c;
};

const int maxpow = 2000;

int n,m,k,x,y,z;
int pos[4002005], power[4002005];
vector<edge> gph[4002005];
int dis[4002005], inq[4002005];
deque<int> nxt;

int f(int i, int j) { //2d to 1d
	return (i-1)*maxpow+j;
}

void spfa() {
	for (int i = 1; i <= n*maxpow+n; i++) dis[i] = 1e9;
	dis[f(pos[1],power[1])] = 0;
	nxt.push_back(f(pos[1],power[1]));
	inq[f(pos[1],power[1])] = 1;
	while (nxt.size()) {
		auto tmp = nxt.front();
		nxt.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]) nxt.push_back(i.v);
				inq[i.v] = 1;
			}
		}
	}
	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