Submission #723969

#	Time	Username	Problem	Language	Result	Execution time	Memory
723969		GrandTiger1729	Sky Walking (IOI19_walk)	C++17	24 / 100	4083 ms	387764 KiB

walk

#include "walk.h"
#ifndef EVAL
#include "grader.cpp"
#endif

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

const long long INF = 1e18;
long long min_distance(vector<int> a, vector<int> h, vector<int> l, vector<int> r, vector<int> b, int S, int T){
	int n = a.size(), m = l.size();
	vector<int> ord(n), dt(m);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](auto x, auto y){
		return h[x] > h[y];
	});
	iota(dt.begin(), dt.end(), 0);
	sort(dt.begin(), dt.end(), [&](auto x, auto y){
		return b[x] > b[y];
	});
	set<int> st;
	map<pair<int, int>, int> mp;
	auto idx = [&](int x, int y) -> int {
		if (mp.find(make_pair(x, y)) == mp.end())
			return mp[make_pair(x, y)] = mp.size();
		return mp[make_pair(x, y)];
	};
	vector<vector<pair<int, int>>> g;
	vector<vector<int>> pos(n);
	{
		int j = 0;
		for (int &i: dt){
			while (j < n && h[ord[j]] >= b[i]){
				st.insert(ord[j]);
				j++;
			}
			// cerr << ":::" << endl;
			auto it = st.lower_bound(l[i]);
			// cerr << *it << endl;
			while (it != st.end() && *it != r[i]){
				auto it2 = it;
				it++;
				int u = idx(*it2, b[i]), v = idx(*it, b[i]);
				pos[*it2].push_back(b[i]);
				pos[*it].push_back(b[i]);
				g.resize(mp.size());
				g[u].emplace_back(v, a[*it] - a[*it2]);
				g[v].emplace_back(u, a[*it] - a[*it2]);
			}
		}
	}
	// cerr << "OK" << endl;
	idx(S, 0), idx(T, 0);
	// cerr << idx(S, 0) << ' ' << idx(T, 0) << endl;
	pos[S].push_back(0);
	pos[T].push_back(0);
	// cerr << endl;
	// for (int i = 0; i < n; i++)
	// 	cerr << pos[i].size() << ' ';
	// cerr << endl;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < (int)pos[i].size() - 1; j++){
			int u = idx(i, pos[i][j]), v = idx(i, pos[i][j + 1]);
			// cerr << u << ' ' << v << endl;
			g.resize(mp.size());
			g[u].emplace_back(v, pos[i][j] - pos[i][j + 1]);
			g[v].emplace_back(u, pos[i][j] - pos[i][j + 1]);
		}
	}
	// cerr << "OK2" << endl;
	int N = g.size();
	// for (int i = 0; i < N; i++)
	// 	for (auto &[v, w]: g[i])
	// 		cerr << i << ' ' << v << ' ' << w << endl;
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
	vector<bool> vis(N);
	vector<long long> dis(N, INF);
	pq.emplace(0, idx(S, 0));
	dis[idx(S, 0)] = 0;
	while (pq.size()){
		auto [d, u] = pq.top();
		pq.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto &[v, w]: g[u]){
			if (dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				pq.emplace(dis[v], v);
			}
		}
	}
	// cerr << endl << g[idx(S, 0)].size() << endl;
	// for (int i = 0; i < N; i++)
	// 	cerr << dis[i] << ' ';
	// cerr << endl;
	long long ans = dis[idx(T, 0)];
	return ans >= INF? -1: ans;
}

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