Submission #1244215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244215		madamadam3	Sky Walking (IOI19_walk)	C++20	0 / 100	4093 ms	1114112 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;

#define en(x) (x).end()
#define bg(x) (x).begin()
#define all(x) bg(x), en(x)
#define sz(x) int(x.size())
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define each(a, x) for (auto &a : x)
using pi = pair<int, int>;

struct Point {
	int x, y, id;

	Point() {};
	Point(int X, int Y, int ID) : x(X), y(Y), id(ID) {};

	const bool operator<(const Point &other) const {
		if (x == other.x && y == other.y) return id < other.id;
		if (x == other.x) return y < other.y;
		return x < other.x;
	}

	int dist(Point &other) {
		return abs(other.x - x) + abs(other.y - y);
	}
};

struct Edge {
	int u, v, dist;
};

struct Line {
	int x, y, h;
};

int pid = 0;
int n, m;

ll min_distance(vi X, vi H, vi L, vi R, vi Y, int s, int g) {
	n = sz(X); m = sz(L);
	vi nid(n), eid(m); iota(all(nid), 0); iota(all(eid), 0);
	sort(all(nid), [&](int a, int b) {return X[a] < X[b];});
	sort(all(eid), [&](int a, int b) {
		if (L[a] == L[b] && R[a] == R[b]) return Y[a] < Y[b];
		if (L[a] == L[b]) return X[R[a]] < X[R[b]];
		return X[L[a]] < X[L[b]]; 
	});

	vvi eadj(m, vi()), badj(n, vi());
	vector<Edge> edges; vector<Point> points; 

	FOR(i, 0, m) {
		FOR(j, 0, n) {
			if (X[j] < X[L[i]]) continue;
			if (X[j] > X[R[i]]) continue;
			if (H[j] < Y[i]) continue;

			int id = pid++;
			points.push_back(Point{X[j], Y[i], id});

			eadj[i].pb(id);
			badj[j].pb(id);
		}

		sort(all(eadj[i]), [&](int a, int b) {return points[a] < points[b];});
		FOR(j, 0, sz(eadj[i]) - 1) {
			edges.pb(Edge{eadj[i][j], eadj[i][j+1], points[eadj[i][j]].dist(points[eadj[i][j+1]])});
		}
	}

	FOR(i, 0, n) {
		points.pb(Point(X[i], 0, pid++));
		points.pb(Point(X[i], H[i], pid++));
		badj[i].pb(pid-2); badj[i].pb(pid-1);

		sort(all(badj[i]), [&](int a, int b) {return points[a] < points[b];});
		FOR(j, 0, sz(badj[i]) - 1) {
			edges.pb(Edge{badj[i][j], badj[i][j+1], points[badj[i][j]].dist(points[badj[i][j+1]])});
		}
	}
	
	int sid = badj[s][0], gid = badj[g][0];
	vvi padj(sz(points), vi());
	for (auto &el : edges) {
		padj[el.u].pb(el.v);
		padj[el.v].pb(el.u);
	}

	int np = sz(points);
	const ll INF = 4e18;
	vector<ll> dist(np, INF), par(np, -1);
	dist[sid] = 0;
	using pl = pair<ll, ll>;
	priority_queue<pl, vector<pl>, greater<pl>> pq;
	pq.push({0, sid});

	while (!pq.empty()) {
		int cur = pq.top().second;	
		ll d = pq.top().first;

		pq.pop();

		for (auto &v : padj[cur]) {
			if (d + points[cur].dist(points[v]) < dist[v]) {
				dist[v] = d + points[cur].dist(points[v]);
				par[v] = cur;
				pq.push({dist[v], v});
			}
		}
	}
	
	// vi path; int cur = gid;
	// while (cur != -1) {
	// 	path.pb(cur);
	// 	cur = par[cur];
	// }

	// reverse(all(path));
	// for (auto &el : path) {
	// 	cout << points[el].x << " " << points[el].y << "\n";
	// }
	return dist[gid];
}

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