Submission #285683

#	Time	Username	Problem	Language	Result	Execution time	Memory
285683		cookiedoth	Sky Walking (IOI19_walk)	C++14	0 / 100	4046 ms	230292 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 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;

vector<int> find_x(bridge B) {
	vector<int> res;
	for (int i = B.l; i <= B.r; ++i) {
		if (B.y <= h[i]) {
			res.push_back(i);
		}
	}
	return res;
}

vector<vector<int> > xc;

void build_xc(int s, int g) {
	// 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];
}

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: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43