Submission #622762

#	Time	Username	Problem	Language	Result	Execution time	Memory
622762		cheissmart	Sky Walking (IOI19_walk)	C++14	33 / 100	4075 ms	23248 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define MP make_pair
#define EB emplace_back
#define PB push_back
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;
const ll oo = 1e18;

vi asr[N], asl[N];
map<int, ll> dist[N];

ll brute(vi& x, vi& h, vi& l, vi& r, vi& y, int s, int g) {
	int n = SZ(x);
	int m = SZ(l);
	vi ys = y;
	ys.PB(0);
	auto get_edges = [&] (int i, int yy) {
		V<pair<pi, int>> res;
		for(int yyy:ys) if(yyy <= h[i]) {
			res.EB(pi(i, yyy), abs(yy - yyy));
		}
		for(int j = 0; j < m; j++) {
			if(y[j] == yy && l[j] <= i && i <= r[i]) {
				for(int k = l[j]; k <= r[j]; k++) if(yy <= h[k]) {
					res.EB(pi(k, yy), abs(x[i] - x[k]));
				}
			}
		}
		return res;
	};
	priority_queue<pair<ll, pi>, V<pair<ll, pi>>, greater<pair<ll, pi>>> pq;
	pq.push(MP(0, pi(s, 0)));
	dist[0][0] = 0;
	
	while(pq.size()) {
		auto[dd, state] = pq.top(); pq.pop();
		auto[i, yy] = state;
		if(dd > dist[i][yy]) continue;
		V<pair<pi, int>> res = get_edges(i, yy);
		for(auto[nstate, w]:res) {
			auto[ni, nyy] = nstate;
			if(dist[ni].count(nyy) == 0 || dd + w < dist[ni][nyy]) {
				dist[ni][nyy] = dd + w;
				pq.push(MP(dd + w, nstate));
			}
		}
	}

	if(dist[g].count(0))
		return dist[g][0];
	return -1;
}

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
	int n = SZ(x);
	int m = SZ(l);
	if(s != 0 || g != n - 1) {
		return brute(x, h, l, r, y, s, g);
	}

	for(int i = 0; i < m; i++) {
		asl[l[i]].PB(y[i]);
		asr[r[i]].PB(y[i]);
	}
	map<int, ll> mp;
	mp[0] = 0;
	asr[0].PB(0);

	for(int i = 0; i < n; i++) {
		set<int> no;
		for(int yy:asl[i]) {
			no.insert(yy);
			auto it = mp.lower_bound(yy);
			ll d = oo;
			if(it != mp.end()) 
				d = min(d, it -> S + abs(yy - it -> F));
			if(it != mp.begin()) {
				it--;
				d = min(d, it -> S + abs(yy - it -> F));
			}
			mp[yy] = d;
		}
		if(i < n - 1) for(int yy:asr[i]) {
			if(no.count(yy)) continue;
			mp.erase(yy);
		}
		if(mp.empty()) return -1;
	}

	ll ans = oo;
	for(auto[yy, d]:mp)
		ans = min(ans, d + yy);
	return ans + x[n - 1] - x[0];
}

Compilation message (stderr)

walk.cpp: In function 'll brute(vi&, vi&, vi&, vi&, vi&, int, int)':
walk.cpp:48:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |   auto[dd, state] = pq.top(); pq.pop();
      |       ^
walk.cpp:49:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |   auto[i, yy] = state;
      |       ^
walk.cpp:52:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |   for(auto[nstate, w]:res) {
      |           ^
walk.cpp:53:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |    auto[ni, nyy] = nstate;
      |        ^
walk.cpp:25:6: warning: unused variable 'n' [-Wunused-variable]
   25 |  int n = SZ(x);
      |      ^
walk.cpp: In function 'll min_distance(vi, vi, vi, vi, vi, int, int)':
walk.cpp:103:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |  for(auto[yy, d]:mp)
      |          ^

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