Submission #328516

#	Time	Username	Problem	Language	Result	Execution time	Memory
328516		negar_a	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1089 ms	9452 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 3e5 + 10;
int n, m;
int inf = 1e9;
int b[maxn], p[maxn];
vector <int> adj[maxn];
int dis[maxn];

int main(){
	fast_io;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i ++){
		scanf("%d %d", b + i, p + i);
		adj[b[i]].pb(i);
	}
	
	for(int i = 0; i <= m; i ++){
		dis[i] = inf;
	}
	
	set <pii> s;
	s.insert({0, 0});
	
	while(s.size()){
		int x = s.begin() -> S;
		int w = s.begin() -> F;
		s.erase(s.begin());
		if(dis[x] >= w){
			dis[x] = w;
			if(x == 1){
				printf("%d", dis[1]);
				return 0;
			}	
			for(int i = b[x]; i <= n; i += p[x]){
				int d = abs(i - b[x]);
				if(d % p[x] == 0){
					for(int u : adj[i]){
						if(dis[u] > dis[x] + (d / p[x])){
							s.erase({dis[u], u});
							dis[u] = dis[x] + (d / p[x]);
							s.insert({dis[u], u});
						}
					}
				}
			}
			for(int i = b[x]; i >= 0; i -= p[x]){
				int d = abs(i - b[x]);
				if(d % p[x] == 0){
					for(int u : adj[i]){
						if(dis[u] > dis[x] + (d / p[x])){
	//						cout << "ii : " << i << " | " << d << " : " << d / p[x] << endl;
							s.erase({dis[u], u});
							dis[u] = dis[x] + (d / p[x]);
							s.insert({dis[u], u});
						}
					}
				}
			}
		}
	}
	
	if(dis[1] != inf){
		printf("%d", dis[1]);
	}else{
		printf("%d", -1);
	}
	
	return 0;
}

Compilation message (stderr)

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

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