Submission #430673

#	Time	Username	Problem	Language	Result	Execution time	Memory
430673		saleh	Sky Walking (IOI19_walk)	C++17	24 / 100	1806 ms	359472 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

#define int long long
#define ft first
#define sd second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 100 * 1000 + 23, MAXV = 1000 * 1000 + 23, MAXE = 4000 * 1000 + 23, INF = 1e15;

int n, m, cnt, dis[MAXV];
vector<int> add[MAXN], del[MAXN], pt[MAXN];
set<pii> s;
map<int, int> mp[MAXN];
vector<pii> pts, g[MAXV];

void dij(int v) {/*
	for (int i = 0; i < cnt; i++) {
		cout << "\\" << i << ": " << pts[i].ft << ' ' << pts[i].sd << endl << '\t';
		for (auto j : g[i]) cout << j.ft << ' ' << j.sd << '\t';
		cout << endl;
	}*/
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, v});
	for (int i = 0; i < cnt; i++) dis[i] = INF;
	dis[v] = 0;
	while (!pq.empty()) {
		pii x = pq.top();
		pq.pop();
		if (x.ft > dis[x.sd]) continue;
		for (auto i : g[x.sd]) if (dis[i.ft] > dis[x.sd] + i.sd) {
			dis[i.ft] = dis[x.sd] + i.sd;
			pq.push({dis[i.ft], i.ft});
		}
	}
}

long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t ss, int32_t gg) {
	int tmp = 0;
	n = x.size();
	m = l.size();
	for (int i = 0; i < m; i++) add[l[i]].push_back(i), del[r[i]].push_back(i);
	for (int j = 0; j < n; j++) {
		for (auto i : add[j]) s.insert({y[i], i});
		if (ss == j && s.size() && s.begin() -> ft <= h[j]) {
			ss = -cnt;
			tmp += s.begin() -> ft;
		} else if (ss == j) return -1;
		if (gg == j && s.size() && s.begin() -> ft <= h[j]) {
			gg = -cnt;
			tmp += s.begin() -> ft;
		} else if (gg == j) return -1;
		pii prev = {-1, -1};
		for (auto i : s) {
			if (i.ft > h[j]) break;
			pts.push_back({i.sd, j});
			mp[i.sd][j] = cnt++;
			pt[i.sd].push_back(j);
			if (prev.sd != -1) g[cnt - 1].push_back({cnt - 2, i.ft - prev.ft}), g[cnt - 2].push_back({cnt - 1, i.ft - prev.ft});
			prev = i;
		}
		for (auto i : del[j]) s.erase({y[i], i});
	}
	ss = -ss;
	gg = -gg;
	for (int i = 0; i < m; i++) for (int j = 1; j < (int)pt[i].size(); j++)
		g[mp[i][pt[i][j - 1]]].push_back({mp[i][pt[i][j]], x[pt[i][j]] - x[pt[i][j - 1]]}), g[mp[i][pt[i][j]]].push_back({mp[i][pt[i][j - 1]], x[pt[i][j]] - x[pt[i][j - 1]]});
	dij(ss);
	return (dis[gg] == INF? -1: dis[gg] + tmp);
}/*
int32_t main() { cout << min_distance({0, 3, 5, 7, 10, 12, 14},
{8, 7, 9, 7, 6, 6, 9},
{0, 0, 0, 2, 2, 3, 4},
{1, 2, 6, 3, 6, 4, 6},
{1, 6, 8, 1, 7, 2, 5},
1, 5); }*/

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