Submission #298519

#	Time	Username	Problem	Language	Result	Execution time	Memory
298519		square1001	Sky Walking (IOI19_walk)	C++14	24 / 100	4054 ms	468852 KiB

walk

#include "walk.h"
#include <set>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1LL << 61;
struct edge {
	int ax, bx, y;
};
struct state {
	int pos; long long cost;
	bool operator<(const state& s) const {
		return cost > s.cost;
	}
};
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int N = x.size(), M = y.size();
	vector<int> compy = h;
	compy.insert(compy.end(), y.begin(), y.end());
	sort(compy.begin(), compy.end());
	compy.erase(unique(compy.begin(), compy.end()), compy.end());
	int S = compy.size();
	vector<vector<int> > layer(S);
	for(int i = 0; i < N; ++i) {
		layer[lower_bound(compy.begin(), compy.end(), h[i]) - compy.begin()].push_back(i);
	}
	for(int i = 0; i < M; ++i) {
		layer[lower_bound(compy.begin(), compy.end(), y[i]) - compy.begin()].push_back(i + N);
	}
	vector<vector<int> > branchy(N, vector<int>({ 0 }));
	vector<edge> E;
	set<int> st;
	for(int i = S - 1; i >= 0; --i) {
		sort(layer[i].begin(), layer[i].end());
		for(int j : layer[i]) {
			if(j < N) {
				st.insert(j);
			}
			else {
				int id = j - N;
				set<int>::iterator it = st.lower_bound(l[id]);
				while(it != st.end() && *it <= r[id]) {
					int px = *it;
					branchy[px].push_back(y[id]);
					++it;
					if(it != st.end() && *it <= r[id]) {
						int qx = *it;
						E.push_back(edge{px, qx, y[id]});
					}
				}
			}
		}
	}
	vector<int> vx, vy;
	vector<int> branchsum(N + 1);
	for(int i = 0; i < N; ++i) {
		sort(branchy[i].begin(), branchy[i].end());
		branchy[i].erase(unique(branchy[i].begin(), branchy[i].end()), branchy[i].end());
		branchsum[i + 1] = branchsum[i] + branchy[i].size();
		for(int j : branchy[i]) {
			vx.push_back(x[i]);
			vy.push_back(j);
		}
	}
	int V = branchsum[N];
	vector<vector<int> > G(V);
	for(int i = 0; i < N; ++i) {
		for(int j = branchsum[i]; j < branchsum[i + 1] - 1; ++j) {
			G[j].push_back(j + 1);
			G[j + 1].push_back(j);
		}
	}
	for(int i = 0; i < int(E.size()); ++i) {
		int pa = lower_bound(branchy[E[i].ax].begin(), branchy[E[i].ax].end(), E[i].y) - branchy[E[i].ax].begin();
		int pb = lower_bound(branchy[E[i].bx].begin(), branchy[E[i].bx].end(), E[i].y) - branchy[E[i].bx].begin();
		int ia = branchsum[E[i].ax] + pa;
		int ib = branchsum[E[i].bx] + pb;
		G[ia].push_back(ib);
		G[ib].push_back(ia);
	}
	priority_queue<state> que;
	que.push(state{branchsum[s], 0});
	vector<long long> dist(V, inf);
	dist[branchsum[s]] = 0;
	vector<bool> vis(V, false);
	while(!que.empty()) {
		int u = que.top().pos; que.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int i : G[u]) {
			long long nd = dist[u] + abs(vx[i] - vx[u]) + abs(vy[i] - vy[u]);
			if(dist[i] > nd) {
				dist[i] = nd;
				que.push(state{i, dist[i]});
			}
		}
	}
	return (dist[branchsum[g]] != inf ? dist[branchsum[g]] : -1LL);
}

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