oj.uz

Submission #1071530

# Submission time Handle Problem Language Result Execution time Memory
1071530 2024-08-23T08:24:15 Z Gromp15 Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 685720 KB 
#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<int> idx(n);
	iota(all(idx), 0);
	sort(all(idx), [&](int x, int y) { return h[x] > h[y]; });
	vector<int> idx2(m);
	iota(all(idx2), 0);
	sort(all(idx2), [&](int X, int Y) { return y[X] > y[Y]; });
	set<int> who;
	vector<ar<int, 3>> edges;
	for (int i = 0, on = 0; i < m; i++) {
		int L = l[idx2[i]], R = r[idx2[i]], H = y[idx2[i]];
		while (on < n && h[idx[on]] >= H) {
			who.insert(idx[on++]);
		}
		int lst = -1;
		auto it1 = who.lower_bound(L);
		if (it1 == who.end() || *it1 > R) continue;
		lst = *it1;
		while (1) {
			auto it = who.upper_bound(lst);
			if (it == who.end() || *it > R) break;
			edges.push_back({lst, *it, H});
			lst = *it;
		}
	}
	vector<vector<int>> nodes(n);
	vector<map<int, vector<int>>> adj(n);
	for (auto [l, r, H] : edges) {
		nodes[l].emplace_back(H);
		nodes[r].emplace_back(H);
		adj[l][H].push_back(r);
		adj[r][H].push_back(l);
	}
	nodes[s].emplace_back(0);
	nodes[g].emplace_back(0);
	for (int i = 0; i < n; i++) {
		sort(all(nodes[i]));
		nodes[i].erase(unique(all(nodes[i])), nodes[i].end());
	}
	vector<map<int, ll>> dist(n);
	dist[s][0] = 0;
	priority_queue<ar<ll, 3>, vector<ar<ll, 3>>, greater<ar<ll, 3>>> q;
	q.push({0, s, 0});
	auto rlx = [&](int v1, int x1, int v2, int x2) {
		ll new_dist = dist[v1][x1] + abs(x[v1] - x[v2]) + abs(x1 - x2);
		if (!dist[v2].count(x2) || dist[v2][x2] > new_dist) {
			dist[v2][x2] = new_dist;
			q.push({dist[v2][x2], v2, x2});
		}
	};
	while (q.size()) {
		auto [cost, v, i] = q.top(); q.pop();
		if (cost != dist[v][i]) continue;
		auto it = upper_bound(all(nodes[v]), i);
		if (it != nodes[v].end() && *it <= h[v]) {
			rlx(v, i, v, *it);
		}
		assert(it != nodes[v].begin());
		it--;
		if (it != nodes[v].begin() && i <= h[v]) {
			rlx(v, i, v, *prev(it));
		}
		for (int x : adj[v][i]) {
			rlx(v, i, x, i);
		}
	}
	return dist[g][0] == INF ? -1 : dist[g][0];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1272 ms 141712 KB Output is correct
4 Correct 799 ms 158960 KB Output is correct
5 Correct 383 ms 99832 KB Output is correct
6 Correct 326 ms 89592 KB Output is correct
7 Incorrect 381 ms 99836 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 15348 KB Output is correct
2 Execution timed out 4088 ms 685720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 15348 KB Output is correct
2 Execution timed out 4088 ms 685720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -