제출 #582961

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

skyscraper

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using pii = pair<int,int>;

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];
priority_queue<pii,vector<pii>,greater<pii>> nxt;

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

string g(int i) {
	if (i > n*n) cout << i-maxpow*n;
	else cout << "(" << i/maxpow+1 << "," << i%maxpow << ")";
	return "";  
}

void dijkstra() {
	for (int i = 1; i <= n*maxpow+n; i++) dis[i] = -1;
	nxt.push({0,f(pos[1],power[1])});
	while (nxt.size()) {
		auto tmp = nxt.top();
		nxt.pop();
		if (dis[tmp.s] != -1) continue;
//		cout << g(tmp.s) << " (" << tmp.f << ")\n";
		dis[tmp.s] = tmp.f;
		for (auto i : gph[tmp.s]) nxt.push({tmp.f+i.c,i.v});
	}
	cout << dis[n*maxpow+pos[2]] << '\n';
}

int main() {
	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});
	dijkstra();
}

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