Submission #298572

#	Time	Username	Problem	Language	Result	Execution time	Memory
298572		square1001	Sky Walking (IOI19_walk)	C++14	24 / 100	1238 ms	121044 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();
	if(s == 0 && g == N - 1 && h == vector<int>(N, h[0])) {
		// subtask 3
		vector<vector<int> > gin(N), gout(N);
		for(int i = 0; i < M; ++i) {
			gin[l[i]].push_back(i);
			gout[r[i]].push_back(i);
		}
		vector<vector<int> > g(N);
		set<pair<int, int> > st;
		for(int i = 0; i < N; ++i) {
			for(int j : gin[i]) {
				st.insert(make_pair(y[j], j));
			}
			for(int j : gout[i]) {
				st.erase(make_pair(y[j], j));
			}
			for(int j : gout[i]) {
				set<pair<int, int> >::iterator it = st.lower_bound(make_pair(y[j], j));
				if(it != st.end()) {
					int id = it->second;
					g[id].push_back(j);
				}
				if(it != st.begin()) {
					int id = (--it)->second;
					g[id].push_back(j);
				}
			}
		}
		vector<int> perm(M);
		for(int i = 0; i < M; ++i) {
			perm[i] = i;
		}
		sort(perm.begin(), perm.end(), [&](int i, int j) { return r[i] < r[j]; });
		vector<long long> dp(M, inf);
		for(int i : perm) {
			if(l[i] == 0) {
				dp[i] = y[i] + x[r[i]];
			}
			for(int j : g[i]) {
				dp[i] = min(dp[i], dp[j] + (x[r[i]] - x[r[j]]) + abs(y[i] - y[j]));
			}
		}
		long long ans = inf;
		for(int i = 0; i < M; ++i) {
			if(r[i] == N - 1) {
				ans = min(ans, dp[i] + y[i]);
			}
		}
		return (ans != inf ? ans : -1);
	}
	else {
		// other subtasks
		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);
	}
	return -1LL;
}

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