oj.uz

Submission #831133

# Submission time Handle Problem Language Result Execution time Memory
831133 2023-08-19T19:19:33 Z PurpleCrayon Sky Walking (IOI19_walk) C++17
0 / 100
 174 ms 26188 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10;
const ll INF = 1e18+10;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

int n, m;
vector<pair<int, int>> adj[N];
ll dist[N];

void add_edge(int a, int b, int w) {
	adj[a].emplace_back(b, w);
	adj[b].emplace_back(a, w);
}

void dijkstra(int S) {
	fill(dist, dist + N, INF);

	min_pq<pair<ll, int>> pq;
	pq.push({dist[S] = 0, S});

	while (!pq.empty()) {
		auto [d_c, c] = pq.top(); pq.pop();
		if (dist[c] != d_c) continue;
		for (auto [nxt, w] : adj[c]) {
			if (dist[nxt] > dist[c] + w) {
				dist[nxt] = dist[c] + w;
				pq.push({dist[nxt], nxt});
			}
		}
	}
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = sz(x), m = sz(l);
	assert(s == 0 && g == n-1);

	auto build = [&]() {
		vector<vector<int>> ev(n);
		for (int i = 0; i < m; i++) {
			ev[l[i]].push_back(i);
			ev[r[i]].push_back(i);
		}

		vector<bool> on(m);
		set<pair<int, int>> s;
		for (int i = 0; i < n; i++) {
			for (int x : ev[i]) if (on[x]) {
				auto me = s.insert({y[x], x}).first;

				{
					auto it = next(me);
					if (it != s.end() && it->first <= h[i]) {
						add_edge(x, it->second, it->first - y[x]);
					}
				}

				{
					if (me != s.begin()) {
						auto it = prev(me);
						add_edge(x, it->second, y[x] - it->first);
					}
				}
			}

			for (int x : ev[i]) if (!on[x]) {
				s.erase({y[x], x});
			}

			for (int x : ev[i]) on[x] = !on[x];
		}
	};

	build();
	int S = m+1;
	for (int i = 0; i < m; i++) if (l[i] == 0) {
		add_edge(S, i, y[i]);
	}
	dijkstra(S);

	ll ans = INF;
	for (int i = 0; i < m; i++) if (r[i] == n-1) {
		ans = min(ans, dist[i] + y[i]);
	}

	// cerr << x[n-1] - x[0] << ' ' << ans << endl;
	if (ans == INF) return -1;
	return ans + x[n-1] - x[0];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11084 KB Output is correct
2 Correct 116 ms 18956 KB Output is correct
3 Correct 112 ms 19396 KB Output is correct
4 Correct 169 ms 25884 KB Output is correct
5 Correct 142 ms 25552 KB Output is correct
6 Correct 174 ms 26016 KB Output is correct
7 Correct 86 ms 18196 KB Output is correct
8 Incorrect 135 ms 26188 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11084 KB Output is correct
2 Correct 116 ms 18956 KB Output is correct
3 Correct 112 ms 19396 KB Output is correct
4 Correct 169 ms 25884 KB Output is correct
5 Correct 142 ms 25552 KB Output is correct
6 Correct 174 ms 26016 KB Output is correct
7 Correct 86 ms 18196 KB Output is correct
8 Incorrect 135 ms 26188 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -