Submission #1244305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244305		madamadam3	Sky Walking (IOI19_walk)	C++20	10 / 100	3167 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;
using pl = pair<ll, 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 Event {
	int x, id; bool walk, first;

	const bool operator<(const Event &other) const {
		if (x == other.x) return walk ? first : !other.first;
		return x < other.x;
	}
};

const ll INF = 4e18;
int n, m, np, pid = 0;
int s, g;
vi X, H, L, R, Y, nid, eid;
vvi eadj, badj, padj;
vector<Edge> edges;
vector<Point> points;

void preprocess() {
	nid.resize(n), eid.resize(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]]; 
	});

	badj.resize(n), eadj.resize(m);
	vector<Event> events; FOR(i, 0, m) events.pb(Event({X[L[i]], i, true, true})), events.pb(Event{X[R[i]], i, true, false});
	FOR(i, 0, n) events.pb(Event{X[i], i, false, false});
	sort(all(events));
	set<pi> active;

	each(evt, events) {
		if (evt.walk) {
			if (evt.first) {
				active.insert({Y[evt.id], evt.id});
			} else {
				active.erase({Y[evt.id], evt.id});
			}
		} else {
			auto itend = active.lower_bound({H[evt.id] + 1, INT_MIN});
			for (auto it = active.begin(); it != itend; ++it) {
				int id = pid++;
				int i = it->second, j = evt.id;
				points.push_back(Point{X[j], Y[i], id});

				eadj[i].pb(id);
				badj[j].pb(id);
			}
		}
	}
	
	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]])});
		}
	}

	np = sz(points);
	padj.assign(np, vi());
	for (auto &el : edges) {
		padj[el.u].pb(el.v);
		padj[el.v].pb(el.u);
	}
}

void dijkstra(int root, vector<ll> &dist, vi &par) {
	dist.assign(np, INF); par.assign(np, -1);
	dist[root] = 0;

	priority_queue<pl, vector<pl>, greater<pl>> pq;
	pq.push({0, root});

	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});
			}
		}
	}
}

void output_path(int gid, vi &par) {
	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";
	}
}

ll min_distance(vi x, vi h, vi l, vi r, vi y, int S, int G) {
	X = x; H = h; L = l; R = r; Y = y; s = S; g = G;

	n = sz(X); m = sz(L);
	preprocess();

	int sid = badj[s][0], gid = badj[g][0];

	vector<ll> dist; vi par;
	dijkstra(sid, dist, par);
	// output_path(gid, par);

	return dist[gid] == INF ? -1 : dist[gid];
}

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