제출 #1243218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243218		bangan	Sky Walking (IOI19_walk)	C++20	14 / 100	405 ms	202536 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<pair<int, int>>> adj(n + 16*m);

	auto add_edge = [&](int v, int u, int w) {
		adj[v].eb(u, w);
		adj[u].eb(v, w);
	};
	vector<vector<int>> add(n), del(n);
	for (int i=0; i<m; i++) {
		add[l[i]].pb(i);
		del[r[i]].pb(i);
	}

	int to_add = n;
	set<pair<int, int>> S;
	vector<pair<int, int>> last(m, MP(-1, -1));

	for (int i=0; i<n; i++) {
		for (int j : add[i]) S.insert(MP(y[j], j));
		int prv_y = 0, prv_v = i;
		for (auto [Y, j] : S) {
			if (h[i]<Y) break;
			add_edge(prv_v, to_add, Y-prv_y);
			{
				auto [k, last_x] = last[j];
				if (k != -1) add_edge(k, to_add, x[i] - last_x);
				last[j] = MP(to_add, x[i]);
			}
			prv_y = Y;
			prv_v = to_add;
			to_add++;
		}
		for (int j : del[i]) S.erase(MP(y[j], j));
	}

	ll ans = dijkstra(adj, s, g);
	if (ans==INF) return -1;
	return ans;
}

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