제출 #1243241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243241		bangan	Sky Walking (IOI19_walk)	C++20	33 / 100	124 ms	18500 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

#define pb push_back
#define eb emplace_back

#define MP make_pair

const ll INF = 1ll << 55;

ll dijkstra(auto adj, int s, int f) {
	int n = adj.size();
	vector<bool> vis(n);
	vector<ll> d(n, INF);
	d[s] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	pq.push(MP(0, s));

	while (!pq.empty()) {
		auto [_, v] = pq.top();
		pq.pop();
		if (vis[v]) continue;
		vis[v] = true;
		for (auto [u, w] : adj[v]) if (d[v]+w < d[u]) {
			d[u] = d[v]+w;
			pq.push(MP(d[u], u));
		}
	}
	return d[f];
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n = x.size();
	int m = l.size();

	vector<vector<int>> add(n), del(n);
	for (int i=0; i<m; i++) {
		add[l[i]].pb(i);
		del[r[i]].pb(i);
	}

	vector<ll> cost(m, INF);
	set<pair<ll, int>> S;
	for (int j : add[0]) {
		S.insert(MP(y[j], j));
		cost[j] = y[j];
	}

	auto ins = [&](int i) {
		auto it = S.upper_bound(MP(y[i], m));
		if (it != S.end()) {
			auto [_, j] = *it;
			cost[i] = min(cost[i], cost[j] + y[j]-y[i]);
		}
		if (it != S.begin()) {
			it--;
			auto [_, j] = *it;
			cost[i] = min(cost[i], cost[j] + y[i]-y[j]);
		}
		if (cost[i] != INF) S.insert(MP(y[i], i));
	};

	auto rem = [&](int i) {
		if (cost[i] == INF) return;
		S.erase(MP(y[i], i));
		auto it = S.upper_bound(MP(y[i], m));
		if (it != S.end()) {
			auto [_, j] = *it;
			cost[j] = min(cost[j], cost[i] + y[j]-y[i]);
		}
		if (it != S.begin()) {
			it--;
			auto [_, j] = *it;
			cost[j] = min(cost[j], cost[i] + y[i]-y[j]);
		}
	};

	for (int i=1; i<n; i++) {
		for (auto j : add[i]) ins(j);
		if (i+1 != n) for (auto j : del[i]) rem(j);
	}
	ll ans = INF;
	for (auto [_, i] : S) ans = min(ans, cost[i]+y[i] + x[n-1]-x[0]);

	if (ans==INF) return -1;
	return ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43