Submission #670919

#	Time	Username	Problem	Language	Result	Execution time	Memory
670919		Dan4Life	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	78 ms	64588 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = (int)2e3+10;
const ll LINF = (ll)1e18;
int n, m, ans, a[maxn], b[maxn], dis[maxn];
bool vis[maxn];
vector<pii> adj[maxn];

int mv(int x, int y){
	int dis = abs(a[x]-a[y]);
	if(dis%b[x]) return LINF;
	return dis/b[x];
}

int dijkstra(int s, int d){
	fill(dis,dis+maxn,LINF); fill(vis, vis+maxn,false);
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,s}); dis[s]=0;
	while(!pq.empty()){
		int a = pq.top().se; pq.pop();
		if(vis[a]) continue; vis[a]=1;
		for(auto u : adj[a]){
			int b = u.fi, w = u.se;
			if(dis[a]+w<dis[b]){
				dis[b]=dis[a]+w;
				pq.push({dis[b],b});
			}
		}
	}
	return dis[d]==LINF?-1:dis[d];
}

int32_t main() {
	cin >> n >> m; ans = LINF;
	for(int i = 0; i < m; i++) cin >> a[i] >> b[i];
	for(int i = 0; i < m; i++)
		for(int j = 0; j < m; j++)
			if(i!=j and mv(i,j)!=LINF) adj[i].pb({j,mv(i,j)});
	cout << dijkstra(0,1);
}

Compilation message (stderr)

skyscraper.cpp: In function 'long long int dijkstra(long long int, long long int)':
skyscraper.cpp:27:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |   if(vis[a]) continue; vis[a]=1;
      |   ^~
skyscraper.cpp:27:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   27 |   if(vis[a]) continue; vis[a]=1;
      |                        ^~~

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