Submission #552632

#	Time	Username	Problem	Language	Result	Execution time	Memory
552632		QwertyPi	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	49 ms	12680 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];
vector<int> q[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;
//	}
	q[0].push_back(A[0][0]);
	fill(dp, dp + n, 1 << 30);
	for(int a = 0; a <= 30000; a++){
		while(q[a].size()){
			int v = q[a].back(); q[a].pop_back();
			if(dp[v] != (1 << 30)) continue;
			dp[v] = a;
			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] > a + d) q[a + d].push_back(j);
				}
			}
		}
	}
	cout << (dp[A[1][0]] == (1 << 30) ? -1 : dp[A[1][0]]) << endl;
}

Compilation message (stderr)

skyscraper.cpp: In lambda function:
skyscraper.cpp:29:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   29 |    return a % i < b % i || a % i == b % i && a < b;
      |                            ~~~~~~~~~~~~~~~^~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:33: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]
   33 |   for(int j = 0; j + 1 < H[i].size(); j++){
      |                  ~~~~~~^~~~~~~~~~~~~

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