Submission #1048849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048849		MercubytheFirst	Sky Walking (IOI19_walk)	C++17	10 / 100	404 ms	1048576 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
using ll = long long;
const ll inf = 1e15 + 37;

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);

template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g) {
	ll n = x.size(), m = l.size();
	l.push_back(-1);
	r.push_back(1e9 + 37);
	y.push_back(0);
	auto intr = [&](ll i, ll j) -> bool
	{
		return l[j] <= i and i <= r[j] and h[i] >= y[j];
	};

	vector<vector<ll> > dist(n, vector<ll>(m + 1, inf));
	min_heap<array<ll, 3> > pq;
	for(ll i = 0; i < m; ++i) {
		if(intr(s, i)) {
			pq.push({y[i], s, i});
			// cout << i << " : " << y[i] << endl;
		}
	}
	while(!pq.empty()) {
		auto [d, i, j] = pq.top();
		pq.pop();
		if(dist[i][j] != inf) {
			continue;
		}
		dist[i][j] = d;
		for(ll ii = 0; ii < n; ++ii) {
			for(ll jj = 0; jj < m; ++jj) {
				if(!intr(ii, jj) or !intr(i, jj) or dist[ii][jj] != inf) {
					continue;
				}
				pq.push({dist[i][j] + abs(y[j] - y[jj]) + abs(x[i] - x[ii]), ii, jj});
			}
		}
	}
	ll ans = inf;
	for(int i = 0; i < m; ++i) {
		if(!intr(g, i)) {
			continue;
		}
		ans = min(ans, dist[g][i] + y[i]);
	}
	if(ans == inf)
		ans = -1;
	return ans;
}


template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
  os << "[";
  for(size_t i = 0; i + 1 < N; ++i) {
    os << a[i] << ", ";
  }
  if(N > 0)
    os << a[N - 1];
  os << "]";
  return os;
}
 
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ") ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << '[';
  for(auto x : v)
    os << x << ", ";
  os << "] ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}
//
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}


/*
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
*/

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