Submission #105293

#	Time	Username	Problem	Language	Result	Execution time	Memory
105293		DystoriaX	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	929 ms	24576 KiB

skyscraper

#include <bits/stdc++.h>

#define eb emplace_back

using namespace std;

int n, m;
int b[30010], p[30010];
vector<int> doge[30010];
const int sq = sqrt(30000) + 3;
const int INF = 1e9;
int dist[sq + 1][30010];
priority_queue<tuple<int, int, int> > pq;

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++){
		scanf("%d%d", &b[i], &p[i]);
		doge[b[i]].eb(p[i]);
	}

	for(int i = 0; i < n; i++)
		for(int j = 0; j <= sq; j++)
			dist[j][i] = INF;
	dist[p[0] > sq ? 0 : p[0]][b[0]] = 0;
	pq.push({0, b[0], p[0]});

	while(!pq.empty()){
		int d, pos, pow;
		tie(d, pos, pow) = pq.top(); pq.pop();
		d = -d;

		if(d != dist[pow > sq ? 0 : pow][pos]) continue;

		if(pow != 0) doge[pos].eb(pow);
		for(auto v : doge[pos]){
			int pow = v;
			if(pow <= sq){
				if(pos + pow < n && dist[pow][pos + pow] > d + 1){
					dist[pow][pos + pow] = d + 1;
					pq.push({-dist[pow][pos + pow], pos + pow, pow});
				}
				if(pos - pow >= 0 && dist[pow][pos - pow] > d + 1){
					dist[pow][pos - pow] = d + 1;
					pq.push({-dist[pow][pos - pow], pos - pow, pow});
				}
			} else {
				int k = 1;
				while(pos + k * pow < n){
					if(dist[0][pos + k * pow] > d + k){
						dist[0][pos + k * pow] = d + k;
						pq.push({-dist[0][pos + k * pow], pos + k * pow, 0});
					}
					k++;
				}

				k = 1;
				while(pos - k * pow >= 0){
					if(dist[0][pos - k * pow] > d + k){
						dist[0][pos - k * pow] = d + k;
						pq.push({-dist[0][pos - k * pow], pos - k * pow, 0});
					}
					k++;
				}
			}
		}
		doge[pos].clear();
	}

	int ans = INF;
	for(int i = 0; i <= sq; i++) ans = min(ans, dist[i][b[1]]);

	printf("%d\n", ans == INF ? -1 : ans);

	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &b[i], &p[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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