Submission #490819

#	Time	Username	Problem	Language	Result	Execution time	Memory
490819		hohohaha	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	406 ms	244996 KiB

skyscraper

// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> table;

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
   fastio();
   int tc = 1;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

///#define int short
//long long
const ld pi = 4 * atan(1.0), eps = 1e-9;

const int maxn = 30000 + 5; 

//using namespace __gnu_pbds;
//gp_hash_table<int, int> table;
//const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
//struct chash {
//    int operator()(int x) const { return x ^ RANDOM; }
//};
//gp_hash_table<key, int, chash> table;

gp_hash_table<int, int> dis[maxn]; 

int n, m; 

int p[maxn]; 
int b[maxn]; 

vector<int> S[maxn]; 

const int bl = 2000; 

int disarray[maxn][bl]; 

const int inf = INT_MAX / 2; 

int * distpt(int i, int j) { 
	if(j < bl) return &disarray[i][j]; 
	auto it = dis[i].find(j); 
	if(it == dis[i].end() ) { 
		return &(dis[i][j] = inf);
	}
	return &(it->se); 
}

void solve() {
	cin >> n >> m; 	
	fori(i, 0, m - 1) { 
		int b, p; cin >> b >> p; 
		::b[i] = b; ::p[i] = p; 
		S[b].eb(p); 
	}
	
	fori(i, 0, n - 1) fori(j, 0, bl - 1) disarray[i][j] = inf; 
	
	disarray[b[0]][0] = 0; 
	
	deque<ii> q; 
	
	q.eb(b[0], 0ll); 
	
	while(!q.empty()) { 
		int i = q.front().fi, j = q.front().se; 
		
		q.of(); 
		
		if(i == b[1]) { 
			cout << *distpt(i, j); 
			return; 
		}
		
		#define ef emplace_front
		
		if(j) { 
			auto nxt = distpt(i, 0), now = distpt(i, j); 
			
//			cout << *now << endl;
			
			if(*nxt > *now) { 
				*nxt = *now; 
				q.ef(i, 0); 
			}
			for(int ti: { i - j, i + j}) { 
				if(ti >= 0 and ti < n) {
					nxt = distpt(ti, j);
					if(*nxt > *now + 1) { 
						*nxt = *now + 1; 
						q.eb(ti, j); 
					}
				}
			}
		}
		
		else { 
			auto now = distpt(i, j); 
			for(int tj: S[i]) { 
				auto nxt = distpt(i, tj); 
				if(*nxt > *now) { 
					*nxt = *now; 
					q.ef(i, tj); 
				}
			}
		} 
	}
	cout << -1; 
}

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