Submission #14435

#	Time	Username	Problem	Language	Result	Execution time	Memory
14435		ainta	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	100 / 100	193 ms	137992 KiB

skyscraper

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
#define N_ 7600000
using namespace std;
int n, m, Num[N_], D[N_], Q1[N_], Q2[N_];
vector<int>E[30100];
map<int, int>Map;
bool be[N_], ed[N_];
struct A{
	int a, b;
}w[30100];
int cnt;
void Make(int a, int b, int x){
	int i;
	be[cnt + 1] = true;
	for (i = b; i < n; i += a){
		++cnt;
		Num[cnt] = i;
		if (x == i) E[x].push_back(cnt);
	}
	ed[cnt] = true;
}
void BFS(int a){
	int i, h = 0, t = 0, tt = 0, x;
	for (i = 0; i <= cnt; i++)D[i] = 999999999;
	D[a] = 0;
	Q1[++t] = a;
	while (t){
		while (h < t){
			x = Q1[++h];
			if (x<n){
				for (i = 0; i<E[x].size(); i++){
					if (D[E[x][i]] > D[x]){
						D[E[x][i]] = D[x];
						Q1[++t] = E[x][i];
					}
				}
			}
			else{
				if (D[Num[x]] > D[x]){
					D[Num[x]] = D[x];
					Q1[++t] = Num[x];
				}
			}
		}
		tt = 0;
		for (i = 1; i <= t; i++){
			if (Q1[i]<n)continue;
			x = Q1[i];
			if (!be[x] && D[x - 1] >D[x] + 1){
				D[x - 1] = D[x] + 1;
				Q2[++tt] = x - 1;
			}
			if (!ed[x] && D[x + 1] > D[x] + 1){
				D[x + 1] = D[x] + 1;
				Q2[++tt] = x + 1;
			}
		}
		for (i = 1; i <= tt; i++)Q1[i] = Q2[i];
		t = tt;
		h = 0;
	}
}
int main(){
	int i, p1, p2, t;
	scanf("%d%d", &n, &m);
	cnt = n;
	for (i = 1; i <= m; i++){
		scanf("%d%d", &w[i].a, &w[i].b);
		t = w[i].b * 30100 + (w[i].a%w[i].b);
		if (!Map[t]){
			Map[t] = cnt + 1;
			Make(w[i].b, w[i].a%w[i].b, w[i].a);
		}
		else{
			E[w[i].a].push_back(Map[t] + w[i].a / w[i].b);
		}
	}
	p1 = w[1].a, p2 = w[2].a;
	BFS(p1);
	printf("%d\n", D[p2] == 999999999 ? -1 : D[p2]);
}

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