Submission #770336

#	Time	Username	Problem	Language	Result	Execution time	Memory
770336		SanguineChameleon	Sky Walking (IOI19_walk)	C++17	10 / 100	1520 ms	527720 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e18L + 20;
const int maxN = 1e5 + 20;
const int max_nodes = maxN * 12;
int X[maxN];
int Y[maxN * 2];
int H[maxN * 2];
int L[maxN];
int R[maxN];
pair<int, int> orderY[maxN * 2];
vector<int> qadd[maxN];
vector<int> qrem[maxN];
vector<int> row[maxN];
vector<int> col[maxN * 2];
long long dist[max_nodes];
vector<pair<int, int>> adj[max_nodes];
map<pair<int, int>, int> points;
int node_cnt;

int get_id(int i, int j) {
	auto it = points.find(make_pair(i, j));
	if (it == points.end()) {
		return points[make_pair(i, j)] = ++node_cnt;
	}
	else {
		return it->second;
	}
}

void add_edge(int i1, int j1, int i2, int j2) {
	int u = get_id(i1, j1);
	int v = get_id(i2, j2);
	int w = abs(X[i1] - X[i2]) + abs(Y[j1] - Y[j2]);
	adj[u].emplace_back(v, w);
	adj[v].emplace_back(u, w);
}

long long min_distance(vector<int> _X, vector<int> _H, vector<int> _L, vector<int> _R, vector<int> _Y, int _S, int _T) {
	int N = _X.size();
	int M = _L.size();
	for (int i = 1; i <= N; i++) {
		X[i] = _X[i - 1];
	}
	for (int i = 1; i <= M; i++) {
		orderY[i] = make_pair(_Y[i - 1], i);
	}
	for (int i = M + 1; i <= M + N; i++) {
		orderY[i] = make_pair(_H[i - M - 1], i);
	}
	sort(orderY + 1, orderY + N + M + 1);
	for (int i = 1; i <= N + M; i++) {
		Y[i] = orderY[i].first;
		H[orderY[i].second] = i;
	}
	for (int i = 1; i <= M; i++) {
		L[i] = _L[i - 1] + 1;
		R[i] = _R[i - 1] + 1;
		qadd[L[i]].push_back(i);
		qrem[R[i]].push_back(i);
	}
	set<int> walks;
	for (int i = 1; i <= N; i++) {
		col[i].push_back(0);
		col[i].push_back(H[M + i]);
		for (auto id: qadd[i]) {
			walks.insert(H[id]);
		}
		auto it = walks.upper_bound(H[M + i]);
		while (it != walks.begin()) {
			it--;
			col[i].push_back(*it);
			row[*it].push_back(i);
		}
		for (auto id: qrem[i]) {
			walks.erase(H[id]);
		}
	}
	for (int i = 1; i <= N; i++) {
		sort(col[i].begin(), col[i].end());
		for (int j = 0; j < (int)col[i].size() - 1; j++) {
			add_edge(i, col[i][j], i, col[i][j + 1]);
		}
	}
	for (int i = 1; i <= M; i++) {
		sort(row[H[i]].begin(), row[H[i]].end());
		for (int j = 0; j < (int)row[H[i]].size() - 1; j++) {
			add_edge(row[H[i]][j], H[i], row[H[i]][j + 1], H[i]);
		}
	}
	int S = get_id(_S + 1, 0);
	int T = get_id(_T + 1, 0);
	for (int i = 1; i <= node_cnt; i++) {
		dist[i] = inf;
	}
	dist[S] = 0;
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> Q;
	Q.emplace(0, S);
	while (!Q.empty()) {
		int u = Q.top().second;
		if (Q.top().first != dist[u]) {
			Q.pop();
			continue;
		}
		Q.pop();
		for (auto e: adj[u]) {
			int v = e.first;
			int w = e.second;
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				Q.emplace(dist[v], v);
			}
		}
	}
	if (dist[T] == inf) {
		return -1;
	}
	else {
		return dist[T];
	}
}

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