Submission #285692

#	Time	Username	Problem	Language	Result	Execution time	Memory
285692		cookiedoth	Sky Walking (IOI19_walk)	C++14	24 / 100	4096 ms	228220 KiB

walk

#include "walk.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <deque>
#include <queue>
#include <algorithm>
#include <string>
#include <cassert>
#include <memory>
#include <numeric>
#include <functional>
#include <random>
#define ll long long
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define length(a) ((int)a.size())

using namespace std;

template<class iterator> void output(iterator begin, iterator end, ostream &out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(const T &x, ostream &out = cerr) {
	output(all(x), out);
}

template<class T> int chkmin(T &a, const T &b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmax(T &a, const T &b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

struct min_st {
	min_st() {}

	vector<pair<ll, int> > t;
	int n;

	void build(const vector<ll> &h, int v, int tl, int tr) {
		if (tl == tr) {
			t[v] = {h[tl], tl};
		} else {
			int tm = (tl + tr) >> 1;
			build(h, v * 2, tl, tm);
			build(h, v * 2 + 1, tm + 1, tr);
			t[v] = max(t[v * 2], t[v * 2 + 1]);
		}
	}

	void init(const vector<ll> &h) {
		n = h.size();
		t.resize(4 * n);
		build(h, 1, 0, n - 1);
	}

	pair<ll, int> get(int l, int r, int v, int tl, int tr) {
		if (r < tl || tr < l) {
			return {-1, -1};
		}
		if (l <= tl && tr <= r) {
			return t[v];
		} else {
			int tm = (tl + tr) >> 1;
			pair<ll, int> res_l = get(l, r, v * 2, tl, tm);
			pair<ll, int> res_r = get(l, r, v * 2 + 1, tm + 1, tr);
			return max(res_l, res_r);
		}
	}

	pair<ll, int> get(int l, int r) {
		pair<ll, int> res = get(l, r, 1, 0, n - 1);
		return res;
	}
};

struct bridge {
	int l, r;
	ll y;
};

int n, m;
vector<ll> x, h;
vector<vector<ll> > good_y;
vector<vector<pair<int, int> > > fwd, bck;
vector<bridge> E;
min_st T;

void add(int l, int r, ll x, vector<int> &res) {
	if (l > r) {
		return;
	}
	pair<ll, int> opt = T.get(l, r);
	// cerr << "opt = " << opt.first << " " << opt.second << endl;
	if (opt.first >= x) {
		// cerr << "add " << opt.second << endl;
		res.push_back(opt.second);
		add(l, opt.second - 1, x, res);
		add(opt.second + 1, r, x, res);
	}
}

vector<int> find_x(bridge B) {
	// cerr << "find_x " << B.l << " " << B.r << " " << B.y << endl;
	vector<int> res;
	add(B.l, B.r, B.y, res);
	return res;
}

vector<vector<int> > xc;

void build_xc(int s, int g) {
	T.init(h);
	// output(all(h));
	// cerr << "sg = " << s << " " << g << endl;
	xc.resize(m);
	good_y.resize(n);
	for (int i = 0; i < m; ++i) {
		xc[i] = find_x(E[i]);
		sort(all(xc[i]));
		for (auto id : xc[i]) {
			good_y[id].push_back(E[i].y);
		}
	}
	good_y[s].push_back(0);
	good_y[g].push_back(0);
	for (int i = 0; i < n; ++i) {
		sort(all(good_y[i]));
		good_y[i].erase(unique(all(good_y[i])), good_y[i].end());
	}
}

void build_graph() {
	fwd.resize(n);
	bck.resize(n);
	for (int i = 0; i < n; ++i) {
		fwd[i].resize(good_y[i].size(), make_pair(-1, -1));
		bck[i].resize(good_y[i].size(), make_pair(-1, -1));
	}
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < (int)xc[i].size() - 1; ++j) {
			int l = xc[i][j], r = xc[i][j + 1];
			int pl = lower_bound(all(good_y[l]), E[i].y) - good_y[l].begin();
			int pr = lower_bound(all(good_y[r]), E[i].y) - good_y[r].begin();
			fwd[l][pl] = {r, pr};
			bck[r][pr] = {l, pl};
		}
	}
}

const ll INF = 1e18;
vector<vector<ll> > d;
vector<vector<int> > used;

void djkstra(int s) {
	d.resize(n);
	used.resize(n);
	for (int i = 0; i < n; ++i) {
		d[i].resize(good_y[i].size(), INF);
		used[i].resize(good_y[i].size(), 0);
	}
	set<pair<ll, pair<int, int> > > S;
	d[s][0] = 0;
	S.insert({0, {s, 0}});
	vector<pair<ll, pair<int, int> > > go;
	while (!S.empty()) {
		int id = S.begin()->second.first;
		int level = S.begin()->second.second;
		S.erase(S.begin());
		if (used[id][level]) {
			continue;
		}
		used[id][level] = 1;
		go.clear();
		if (fwd[id][level] != make_pair(-1, -1)) {
			go.emplace_back(x[fwd[id][level].first] - x[id], fwd[id][level]);
		}
		if (bck[id][level] != make_pair(-1, -1)) {
			go.emplace_back(x[id] - x[bck[id][level].first], bck[id][level]);
		}
		if (level < (int)good_y[id].size() - 1) {
			go.emplace_back(good_y[id][level + 1] - good_y[id][level], make_pair(id, level + 1));
		}
		if (level > 0) {
			go.emplace_back(good_y[id][level] - good_y[id][level - 1], make_pair(id, level - 1));
		}
		for (auto ppp : go) {
			if (chkmin(d[ppp.second.first][ppp.second.second], d[id][level] + ppp.first)) {
				S.insert({d[ppp.second.first][ppp.second.second], ppp.second});
			}
		}
	}
}

ll solve(int s, int g) {
	build_xc(s, g);
	// cerr << "build_xc" << endl;			
	build_graph();
	djkstra(s);
	return (d[g][0] == INF ? -1 : d[g][0]);
}

ll min_distance(vector<int> _x, vector<int> _h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = _x.size();
	x.resize(n);
	h.resize(n);
	for (int i = 0; i < n; ++i) {
		x[i] = (ll)_x[i];
		h[i] = (ll)_h[i];
	}
	m = l.size();
	for (int i = 0; i < m; ++i) {
		E.push_back({l[i], r[i], y[i]});
	}
	ll res = solve(s, g);
	return res;
}

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