Submission #513746

#	Time	Username	Problem	Language	Result	Execution time	Memory
513746		BlackWhite	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	1096 ms	199084 KiB

skyscraper

// author: BlackWhite
#include <bits/stdc++.h>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define debugg(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
	for ( \
		auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
		blockTime.second; \
		debugg("%s: %d ms\n", d, (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
	)

#define int long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll oo = 1e18;
const ld eps = 1e-9;
const string yes = "YES";
const string no = "NO";
const ld PI = acos(-1.0);
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair<ii,ii> iv;
typedef vector <int> vi;
typedef vector <vi> vvi;
typedef vector <ii> vp;
#define all(x) begin(x), end(x)
#define sz(x) ((int) x.size())
#define clrscr system("cls");
#define ENDL printf("\n");
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ins insert
#define pob pop_back
#define pof pop_front
#define el '\n'

#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define NAME "test"
inline void io(int x){
	if (!x){
		freopen(NAME".inp", "r", stdin);
		return;
	}
	if (x == 1){
		freopen(NAME".inp", "r", stdin);
		freopen(NAME".out", "w", stdout);
		return;
	}
	freopen(NAME".out", "w", stdout);
}

int n, m;
const int N = 3e4 + 5;
ii sv[N];
vi p[N];
vector <vector <int>> dist(N);

void dijkstra(int s, int t, int minn, int maxx){
	for (int i = 1; i <= n; i++){
		dist[i].resize(n + 5, oo);
	}

	priority_queue <iii, vector <iii>, greater <iii>> pq;

	for (int x : p[s]){
		dist[s][x] = 0;
		pq.push(iii(0, ii(s, x)));
	}

	while(sz(pq)){
		int du = pq.top().fi;
		int u = pq.top().se.fi;
		int pw = pq.top().se.se;

		pq.pop();

		// debug(du, u, pw);

		if (u == t){
			cout << du << el;

			return;
		}

		if (u - pw >= 1 && dist[u - pw][pw] > du){
			dist[u - pw][pw] = du + 1;

			pq.push(iii(dist[u - pw][pw], ii(u - pw, pw)));
		}

		if (u + pw <= n && dist[u + pw][pw] > du){
			dist[u + pw][pw] = du + 1;

			pq.push(iii(dist[u + pw][pw], ii(u + pw, pw)));
		}

		for (int new_pw : p[u]){
			if (u - new_pw >= 1 && dist[u - new_pw][new_pw] > du){
				dist[u - new_pw][new_pw] = du + 1;

				pq.push(iii(dist[u - new_pw][new_pw], ii(u - new_pw, new_pw)));
			}

			if (u + new_pw <= n && dist[u + new_pw][new_pw] > du){
				dist[u + new_pw][new_pw] = du + 1;

				pq.push(iii(dist[u + new_pw][new_pw], ii(u + new_pw, new_pw)));
			}
		}
	}

	int res = oo;

	for (int i = minn; i <= maxx; i++){
		res = min(res, dist[t][i]);
	}

	cout << (res == oo ? -1 : res) << el;
}

inline void solve(){
	cin >> n >> m;
	int minn = oo, maxx = -1;
	for (int i = 1; i <= m; i++){
		cin >> sv[i].fi >> sv[i].se;

		sv[i].fi++;

		p[sv[i].fi].pb(sv[i].se);

		minn = min(minn, sv[i].se);
		maxx = max(maxx, sv[i].se);
	}

	dijkstra(sv[1].fi, sv[2].fi, minn, maxx);
}

signed main()
{
	Fast
	// io(1);

	int test_case = 1;
	// cin >> test_case;
	for (int tt = 1; tt <= test_case; tt++){
		// cout << "Case #" << tt << ": ";

		solve();
	}

	return 0;
}

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