Submission #834981

#	Time	Username	Problem	Language	Result	Execution time	Memory
834981		tranxuanbach	Sky Walking (IOI19_walk)	C++17	24 / 100	4089 ms	683308 KiB

walk

#include "walk.h"

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

#define isz(a) ((signed)a.size())

using ll = long long;
template <class T>
using min_heap = priority_queue <T, vector <T>, greater <T>>;

const int N = 1e5 + 5;

struct building{
	int x, h;
	int idx;

	friend bool operator< (const building& lhs, const building& rhs){
		return lhs.h < rhs.h;
	}
};

struct skywalk{
	int l, r, y;
	int idx;

	friend bool operator< (const skywalk& lhs, const skywalk& rhs){
		return lhs.y < rhs.y;
	}
};

int n, m;
building a[N];
skywalk b[N];
int s, t;

namespace subtask12{
	bool check(){
		return true;
	}

	vector <vector <int>> pos_y;
	vector <map <int, vector <pair <int, int>>>> adj;
	vector <map <int, ll>> dist;
	min_heap <tuple <ll, int, int>> pq;

	void transition(ll d, int x, int y){
		auto itr = dist[x].find(y);
		if (itr == dist[x].end()){
			dist[x][y] = d;
			pq.emplace(d, x, y);
		}
		else if (itr->second > d){
			itr->second = d;
			pq.emplace(d, x, y);
		}
	}

	ll solve(){
		pos_y.resize(n);
		pos_y[s].emplace_back(0);
		pos_y[t].emplace_back(0);
		adj.resize(n);
		dist.resize(n);

		{
			set <int> alive;
			for (int i = 0; i < n; i++){
				alive.emplace(i);
			}
			int ib = 0;
			vector <building> sa(a, a + n);
			sort(sa.begin(), sa.end());
			for (auto &[x, h, ia]: sa){
				while (ib < m and b[ib].y <= h){
					auto itr = alive.lower_bound(b[ib].l);
					int pre = -1;
					while (itr != alive.end() and *itr <= b[ib].r){
						if (not pos_y[*itr].empty()){
							auto u = pair{*itr, pos_y[*itr].back()}, v = pair{*itr, b[ib].y};
							adj[u.first][u.second].emplace_back(v);
							adj[v.first][v.second].emplace_back(u);
						}
						pos_y[*itr].emplace_back(b[ib].y);
						if (pre != -1){
							auto u = pair{pre, b[ib].y}, v = pair{*itr, b[ib].y};
							adj[u.first][u.second].emplace_back(v);
							adj[v.first][v.second].emplace_back(u);
						}
						pre = *itr;
						itr++;
					}
					ib++;
				}
				alive.erase(ia);
			}
		}
		transition(0ll, s, 0);
		while (not pq.empty()){
			auto [d, x, y] = pq.top(); pq.pop();
			if (d > dist[x][y]){
				continue;
			}
			if (x == t and y == 0){
				return d;
			}
			for (auto [tx, ty]: adj[x][y]){
				ll td = d + (abs(a[x].x - a[tx].x) + abs(y - ty));
				transition(td, tx, ty);
			}
		}
		return -1;
	}
}

ll min_distance(vector <int> _x, vector <int> _h, vector <int> _l, vector <int> _r, vector <int> _y, int _s, int _t){
	n = isz(_x); m = isz(_l);
	for (int i = 0; i < n; i++){
		int x = _x[i], h = _h[i];
		a[i] = building{x, h, i};
	}
	for (int i = 0; i < m; i++){
		int l = _l[i], r = _r[i], y = _y[i];
		b[i] = skywalk{l, r, y, i};
	}
	sort(b, b + m);
	s = _s; t = _t;

	if (subtask12::check()){
		return subtask12::solve();
	}
}

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:132:1: warning: control reaches end of non-void function [-Wreturn-type]
  132 | }
      | ^

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