제출 #490817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490817		hohohaha	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	13 ms	15988 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>

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 long long
const ld pi = 4 * atan(1.0), eps = 1e-9;

const int maxn = 2e5 + 5; 

unordered_map<int, int> dis[maxn]; 

int n, m; 

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

vector<int> S[maxn]; 

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); 
	}
	
	dis[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 << dis[i][j] ; 
			return; 
		}
		
		#define ef emplace_front
		
		if(j) { 
			if(!dis[i].count(0) or dis[i][0] > dis[i][j]) { 
				dis[i][0] = dis[i][j]; 
				q.ef(i, 0); 
			}
			for(int ti: { i - j, i + j}) { 
				if(ti >= 0 and ti < n) {
					if(!dis[ti].count(j) or dis[ti][j] > dis[i][j] + 1) { 
						dis[ti][j] = dis[i][j] + 1; 
						q.eb(ti, j); 
					}
				}
			}
		}
		
		else { 
			for(int tj: S[i]) { 
				if(!dis[i].count(tj) or dis[i][tj] > dis[i][0]) { 
					dis[i][tj] = dis[i][0]; 
					q.ef(i, tj); 
				}
			}
		}
	}
}

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