Submission #1071136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071136		Gromp15	Sky Walking (IOI19_walk)	C++17	10 / 100	4098 ms	1048576 KiB

walk

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#include "walk.h"
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

const ll INF = 1e18;

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 = sz(x), m = sz(l);
	vector<vector<int>> inter(n);
	for (int i = 0; i < m; i++) {
		for (int j = l[i]; j <= r[i]; j++) {
			inter[j].emplace_back(y[i]);
		}
	}
	vector<ar<int, 3>> edges;
	for (int i = 0; i < m; i++) edges.push_back({y[i], l[i], r[i]});
	sort(all(edges));
	inter[s].emplace_back(0);
	inter[g].emplace_back(0);
	for (int i = 0; i < n; i++) sort(all(inter[i])), inter[i].erase(unique(all(inter[i])), inter[i].end());
	vector<vector<ll>> dist(n);
	for (int i = 0; i < n; i++) {
		dist[i].resize(sz(inter[i]), INF);
	}
	priority_queue<ar<ll, 3>, vector<ar<ll, 3>>, greater<ar<ll, 3>>> q;
	q.push({0, s, 0});
	dist[s][0] = 0;
	while (q.size()) {
		auto [cost, v, i] = q.top(); q.pop();
		if (cost != dist[v][i]) continue;
		if (i && inter[v][i] <= h[v] && ckmin(dist[v][i-1], dist[v][i] + abs(inter[v][i-1] - inter[v][i]))) {
			q.push({dist[v][i-1], v, i-1});
		}
		if (i+1 < sz(inter[v]) && inter[v][i+1] <= h[v] && ckmin(dist[v][i+1], dist[v][i] + abs(inter[v][i] - inter[v][i+1]))) {
			q.push({dist[v][i+1], v, i+1});
		}
		if (v) {
			auto it1 = upper_bound(all(edges), ar<int, 3>{inter[v][i], v-1, INT_MAX});
			if (it1 == edges.begin() || (*prev(it1))[0] != inter[v][i]) {}
			else {
				auto [y, l, r] = *prev(it1);
				if (l < v && r >= v) {
					auto it = lower_bound(all(inter[v-1]), inter[v][i]);
					if (it != inter[v-1].end() && *it == inter[v][i]) {
						int pos = it - inter[v-1].begin();
						if (ckmin(dist[v-1][pos], dist[v][i] + abs(x[v-1] - x[v]))) {
							q.push({dist[v-1][pos], v-1, pos});
						}
					}
				}
			}
		}
		if (v+1 < n) {
			auto it1 = upper_bound(all(edges), ar<int, 3>{inter[v][i], v, INT_MAX});
			if (it1 == edges.begin() || (*prev(it1))[0] != inter[v][i]) continue;
			auto [y, l, r] = *prev(it1);
			if (l <= v && r >= v+1) {
				auto it = lower_bound(all(inter[v+1]), inter[v][i]);
				if (it != inter[v+1].end() && *it == inter[v][i]) {
					int pos = it - inter[v+1].begin();
					if (ckmin(dist[v+1][pos], dist[v][i] + abs(x[v+1] - x[v]))) {
						q.push({dist[v+1][pos], v+1, pos});
					}
				}
			}
		}
	}
	return dist[g][0] == INF ? -1 : dist[g][0];
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:44:64: warning: narrowing conversion of '(v - 1)' from 'std::tuple_element<1, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   44 |    auto it1 = upper_bound(all(edges), ar<int, 3>{inter[v][i], v-1, INT_MAX});
      |                                                               ~^~
walk.cpp:60:63: warning: narrowing conversion of 'v' from 'std::tuple_element<1, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   60 |    auto it1 = upper_bound(all(edges), ar<int, 3>{inter[v][i], v, INT_MAX});
      |                                                               ^

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