Submission #1155702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155702		gyg	Sky Walking (IOI19_walk)	C++20	24 / 100	4065 ms	551304 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second
#define pq priority_queue
const int N = 2e6 + 5, INF = 1e18;

map<pii, int> nd;
map<int, vec<int>> pnt;
map<int, vec<pii>> adj; // {node, distance}
int st, fn;

arr<bool, N> vs;
arr<int, N> dst;
pq<pii, vec<pii>, greater<pii>> ord;
void djk() {
	dst.fill(INF);

	dst[st] = 0, ord.push({0, st});
	while (ord.size()) {
		int u = ord.top().sec; ord.pop();
		if (vs[u]) continue;
		vs[u] = true;
		for (pii x : adj[u]) {
			int nw_dst = dst[u] + x.sec;
			if (nw_dst >= dst[x.fir]) continue;
			dst[x.fir] = nw_dst, ord.push({nw_dst, x.fir});
		}
	}
}

int min_distance(vec<sig> _x, vec<sig> _h, vec<sig> _l, vec<sig> _r, vec<sig> _y, sig _s, sig _f) {
	vec<vec<int>> twr, wlk;
	for (int i = 0; i < _x.size(); i++) {
		vec<int> x = {_h[i], _x[i]};
		twr.push_back(x);
	}
	for (int i = 0; i < _l.size(); i++) {
		vec<int> x = {_y[i], _x[_l[i]], _x[_r[i]]};
		wlk.push_back(x);
	}
	sort(twr.begin(), twr.end()), sort(wlk.begin(), wlk.end());

	for (int i = 0; i < _x.size(); i++) {
		int id = nd.size() + 1;
		nd[{_x[i], 0}] = id;
		pnt[_x[i]].push_back(0);
	}

	set<int> ps;
	while (wlk.size()) {
		vec<int> x = wlk.back(); wlk.pop_back();
		
		while (twr.size() && twr.back()[0] >= x[0]) {
			vec<int> y = twr.back(); twr.pop_back();
			ps.insert(y[1]);
		}

		for (auto it = ps.find(x[1]); it != ps.end(); it++) {
			if (!nd.count({*it, x[0]})) {
				int id = nd.size() + 1;
				nd[{*it, x[0]}] = id;
				pnt[*it].push_back(x[0]);
			}
			if (*it != x[1]) {
				int u = nd[{*it, x[0]}], v = nd[{*next(it, -1), x[0]}], d = *it - *next(it, -1);
				adj[u].push_back({v, d}), adj[v].push_back({u, d});
			}
			if (*it == x[2]) break;
		}
	}

	for (pair<int, vec<int>> x : pnt) {
		sort(x.sec.begin(), x.sec.end());
		for (int i = 0; i < x.sec.size() - 1; i++) {
			int u = nd[{x.fir, x.sec[i]}], v = nd[{x.fir, x.sec[i + 1]}], d = x.sec[i + 1] - x.sec[i];
			adj[u].push_back({v, d}), adj[v].push_back({u, d});
		}
	}

	// for (pair<pii, int> x : nd) {
	// 	cout << x.fir.fir << " " << x.fir.sec << endl;
	// }

	st = nd[{_x[_s], 0}], fn = nd[{_x[_f], 0}];
	djk();
	if (!vs[fn]) return -1;
	return dst[fn];
}

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