Submission #552631

#	Time	Username	Problem	Language	Result	Execution time	Memory
552631		QwertyPi	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1002 ms	29216 KiB

skyscraper

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
int dp[30001];
vector<int> G[30001];
int A[30001][2];
int l[30001], r[30001];

vector<pii> H[30001];
int main(){
	int n, k;
	cin >> n >> k;
	set<pii> M;
	for(int i = 0; i < k; i++){
		cin >> A[i][0] >> A[i][1];
		if(i >= 2 && M.count({A[i][0], A[i][1]})){
			continue;
		}
		M.insert({A[i][0], A[i][1]});
		G[A[i][0]].push_back(i);
		H[A[i][1]].push_back({A[i][0], i});
	}
	for(int i = 1; i <= 30000; i++){
		sort(H[i].begin(), H[i].end(), [&i](pii aa, pii bb){
			int a = aa.fi, b = bb.fi;
			return a % i < b % i || a % i == b % i && a < b; 
		});
		if(H[i].size() == 0) continue;
		l[H[i].front().se] = H[i].front().fi % i;
		for(int j = 0; j + 1 < H[i].size(); j++){
			if(H[i][j].fi % i == H[i][j + 1].fi % i){
				r[H[i][j].se] = H[i][j + 1].fi;
				l[H[i][j + 1].se] = H[i][j].fi;
			}else{
				r[H[i][j].se] = n - 1;
				l[H[i][j + 1].se] = H[i][j + 1].fi % i;
			}
		}
		r[H[i].back().se] = n - 1;
	}
//	for(int i = 0; i < k; i++){
//		cout << l[i] << ' ' << r[i] << endl;
//	}
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
	q.push({0, A[0][0], 1 << 30});
	fill(dp, dp + n, 1 << 30);
	while(q.size()){
		tuple<int, int, int> qe = q.top(); q.pop();
		int w = get<0>(qe), v = get<1>(qe), ban = get<2>(qe);
		if(dp[v] != (1 << 30)) continue;
		dp[v] = w;
		for(auto i : G[v]){
			for(int j = l[i]; j <= r[i]; j += A[i][1]){
				int d = abs(v - j) / A[i][1];
				if(dp[j] > w + d) q.push({w + d, j, i});
			}
		}
	}
	cout << (dp[A[1][0]] == (1 << 30) ? -1 : dp[A[1][0]]) << endl;
}

Compilation message (stderr)

skyscraper.cpp: In lambda function:
skyscraper.cpp:28:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   28 |    return a % i < b % i || a % i == b % i && a < b;
      |                            ~~~~~~~~~~~~~~~^~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int j = 0; j + 1 < H[i].size(); j++){
      |                  ~~~~~~^~~~~~~~~~~~~
skyscraper.cpp:51:39: warning: unused variable 'ban' [-Wunused-variable]
   51 |   int w = get<0>(qe), v = get<1>(qe), ban = get<2>(qe);
      |                                       ^~~

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