Submission #1263959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263959		_rain_	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1094 ms	47028 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i , a , b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1) << (x))
#define BIT(mask , x) (((mask)>>(x))&(1))
#define sz(x) (int)(x).size()

template<class T1 , class T2>	
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() ,data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}

const int N = (int) 3e4;
const LL inf = (LL)1e18;
const int MAXBLOCK = 174;
	int n , m;
	int b[N + 2] , p[N + 2];

	vector<int>jump_step[N + 2];
	
	struct Node{
		int u;
		int step;
		LL cost;
		bool operator < (const Node&other) const{
			return cost > other.cost;
		}
	};
	
	LL dist[N + 2][MAXBLOCK + 2];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ; 
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}	

		cin >> n >> m;
		for(int i = 1; i <= m; ++i){
			cin >> b[i] >> p[i];
			++b[i];
			jump_step[b[i]].push_back(p[i]);
		}
		for(int i = 1; i <= n; ++i) compress(jump_step[i]);
		memset(dist , 0x3f , sizeof dist);
		dist[b[1]][0] = 0;
		priority_queue<Node> pq;
		pq.push({b[1] , 0 , dist[b[1]][0]});
		
		LL ans = inf;
		
		while (sz(pq)){
			int u = pq.top().u;
			int step = pq.top().step;
			LL cost = pq.top().cost;
			pq.pop();
			if (cost !=dist[u][step]) continue;
			
			if (u == b[2]){
				minimize(ans , dist[u][step]);
				break;
			}
			
			if (step > 0 && u - step > 0 && minimize(dist[u - step][step] , cost + 1)) {
				pq.push({u - step , step , dist[u - step][step]});
			}
			if (step > 0 && u + step <= n && minimize(dist[u + step][step] , cost + 1)){
				pq.push({u + step , step , dist[u + step][step]});
			}
			
			for(int nxt_step : jump_step[u]){
				if (nxt_step >= MAXBLOCK){
					for(int j = u + nxt_step , add = 1; j <= n; j += nxt_step , ++add) {
						if (minimize(dist[j][0] , cost + add)){
							pq.push({j , 0 , dist[j][0]});
						}
					}
					for(int j = u - nxt_step, add = 1; j >= 1; j -= nxt_step , ++add){
						if (minimize(dist[j][0] , cost + add)){
							pq.push({j , 0 , dist[j][0]});
						}
					}
				}
				else {
					int nxt_v = u + nxt_step;
					int prev_v = u - nxt_step;
					if (nxt_v <= n && minimize(dist[nxt_v][nxt_step] , cost + 1)){
						pq.push({nxt_v , nxt_step , dist[nxt_v][nxt_step]});
					}
					if (prev_v > 0 && minimize(dist[prev_v][nxt_step] , cost + 1)){
						pq.push({prev_v , nxt_step , dist[prev_v][nxt_step]});
					}
				}
			}
		}
		if (ans == inf) ans = -1;
		cout << ans;
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:52:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:53:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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