Submission #14388

#	Time	Username	Problem	Language	Result	Execution time	Memory
14388		kriii	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	148 ms	8308 KiB

skyscraper

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int P,N,B[30003],V[30003]; vector<int> G[30003];
int c,u[2][60003],v[2][60003],d[30003];
set<int> chk[30003];

void add(int t, int x)
{
	u[t][c] = B[x]; v[t][c] = +V[x]; c++;
	u[t][c] = B[x]; v[t][c] = -V[x]; c++;
}

int main()
{
	scanf ("%d %d",&P,&N);
	for (int i=0;i<P;i++) d[i] = -1;
	for (int i=0;i<N;i++){
		scanf ("%d %d",&B[i],&V[i]);
		G[B[i]].push_back(i);
	}
	d[B[0]] = 0;
	for (int x : G[B[0]]) add(0,x);
	for (int p=1;;p++){
		int lc = c; c = 0; bool ed = 1;
		int pr = (p + 1) % 2, nx = p % 2;
		for (int i=0;i<lc;i++){
			u[pr][i] += v[pr][i];
			if (0 <= u[pr][i] && u[pr][i] < P){
				ed = 0;
				if (!chk[u[pr][i]].count(abs(v[pr][i]))){
					u[nx][c] = u[pr][i]; v[nx][c] = v[pr][i]; c++;
				}
				if (d[u[pr][i]] == -1){
					d[u[pr][i]] = p; ed = 0;
					chk[u[pr][i]].insert(abs(v[pr][i]));
					for (int x : G[u[pr][i]]){
						if (abs(v[pr][i]) != V[x]){
							add(nx,x);
							chk[u[pr][i]].insert(V[x]);
						}
					}
				}
			}
		}
		if (ed) break;
	}

	printf ("%d\n",d[B[1]]);

	return 0;
}

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