Submission #14385

#	Time	Username	Problem	Language	Result	Execution time	Memory
14385		woqja125	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	738 ms	25320 KiB

skyscraper

#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
const int BUC = 175;
int b[30001], p[30001], n, m;
int dist[(BUC+1)*30000+10];
struct node
{
	int m, n;
	node(int M, int N):n(N){if(M>BUC)M=0; m=M;}
	node(){m=n=0;}
	node(int x):n(b[x])
	{
		if(p[x] <= BUC) m = p[x];
		else m = 0;
	}
	bool operator<(const node &A) const{return false;}
};
int& d(const node &A){return dist[A.n*(BUC+1)+A.m];}
std::vector<int> blist[30001];
void add(int P, int B, int nd, priority_queue<pair<int, node> > &Q)
{
	//printf("##%d %d %d\n", P, B, nd);
	if(B<0 || B>=n) return;
	node X(P, B);
	if(d(X) == -1 || d(X) > nd)
	{
		d(X)=nd;
		Q.push(make_pair(-d(X), X));
	}
}
int abs(int x){return x>0?x:-x;}
int main()
{
	int i;
	scanf("%d%d", &n, &m);
	for(i=0; i<m; i++) scanf("%d%d", b+i, p+i);
	for(i=0; i<m; i++) blist[b[i]].push_back(p[i]);

	priority_queue<pair<int, node> > Q;
	Q.push(make_pair(0, node(0)));
	memset(dist, -1, sizeof(dist));
	d(node(0)) = 0;
	//printf("-%d %d %d\n", dist[352], dist[353], dist[354]);
	while(!Q.empty())
	{
		node x = Q.top().second;
		if(d(x) != -Q.top().first)
		{
			Q.pop();
			continue;
		}
		Q.pop();
		if(x.n==b[1] && x.m == 0) break;
		if(x.m == 0) for(auto pp: blist[x.n])
		{
			if(pp <= BUC) add(pp, x.n, d(x), Q);
			else for(i=x.n%pp; i<n; i+=pp) add(0, i, d(x)+abs(i-x.n)/pp, Q);
		}
		else
		{
			add(0, x.n, d(x), Q);
			add(x.m, x.n+x.m, d(x)+1, Q);
			add(x.m, x.n-x.m, d(x)+1, Q);
		}
	}
	printf("%d\n", d(node(0, b[1])));
	return 0;
}

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