Submission #15720

#	Time	Username	Problem	Language	Result	Execution time	Memory
15720		cki86201	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	100 / 100	216 ms	112340 KiB

skyscraper

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<queue>
using namespace std;

#define X first
#define Y second
typedef pair<int, int> Pi;
const int MX = 30003;
const int SX = 170;

priority_queue <Pi, vector<Pi>, greater<Pi> > pq;
vector <Pi> E[MX];
int n, m;
int p[MX][2];
int chk[MX][SX + 4];
int len[MX], out[MX];

int main(){
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++){
		scanf("%d%d", p[i], p[i] + 1);
		if (p[i][1] < SX){
			if (!chk[p[i][0]][p[i][1]])chk[p[i][0]][p[i][1]] = 1;
			else out[i] = 1;
		}
	}
	for (int i = 0; i < m; i++){
		if (out[i])continue;
		for (int j = p[i][0] - p[i][1], l = 1; j >= 0; j -= p[i][1], l++){
			E[p[i][0]].push_back(Pi(j, l));
			if (p[i][1] < SX && chk[j][p[i][1]])break;
		}
		for (int j = p[i][0] + p[i][1], l = 1; j < n; j += p[i][1], l++){
			E[p[i][0]].push_back(Pi(j, l));
			if (p[i][1] < SX && chk[j][p[i][1]])break;
		}
	}
	pq.push(Pi(0, p[0][0]));
	for (int i = 0; i < n; i++)len[i] = (int)1e9;
	len[p[0][0]] = 0;
	while (!pq.empty()){
		Pi t = pq.top();
		pq.pop();
		if (len[t.Y] != t.X)continue;
		if (t.Y == p[1][0])break;
		for (int i = 0; i < (int)E[t.Y].size(); i++){
			Pi &w = E[t.Y][i];
			if (len[w.X] > len[t.Y] + w.Y){
				len[w.X] = len[t.Y] + w.Y;
				pq.push(Pi(len[w.X], w.X));
			}
		}
	}
	printf("%d", len[p[1][0]] == (int)1e9 ? -1 : len[p[1][0]]);
	return 0;
}

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