oj.uz

Submission #831196

# Submission time Handle Problem Language Result Execution time Memory
831196 2023-08-19T21:55:24 Z PurpleCrayon Sky Walking (IOI19_walk) C++17
33 / 100
 274 ms 49232 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 = 6e5+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, ll>> adj[N];
ll dist[N], extra[N]; // extra cost for the nodes

void add_edge(int a, int b, ll w) {
	// cerr << "add: " << a << ' ' << b << ' ' << w << endl;
	adj[a].emplace_back(b, w);
	adj[b].emplace_back(a, w);
}

void dijkstra(int S) {
	fill(dist, dist + N, INF);
	for (int a = 0; a < N; a++) {
		for (auto& [b, w] : adj[a]) {
			w += extra[b];
		}
	}

	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);

	
	vector<int> nl, nr, ny;
	for (int i = 0; i < m; i++) {
		if (l[i] < s && r[i] > s) {
			bool has = 0;
			for (int j = s; j <= g; j++) if (h[j] >= y[i]) {
				has = 1;
			}

			if (!has) {
				int one = s;
				int two = g;
				while (h[one] < y[i]) one--;
				while (h[two] < y[i]) two++;
				l[i] = one, r[i] = two;
				extra[sz(nl)] += x[s] - x[l[i]] + x[r[i]] - x[g];
				nl.push_back(l[i]);
				nr.push_back(r[i]);
				ny.push_back(y[i]);
				continue;
			}
		}

		if (l[i] < s && r[i] >= s) {
			int one = s-1;
			while (one >= l[i] && h[one] < y[i]) one--;
			int two = s;
			while (two <= r[i] && h[two] < y[i]) two++;

			// [l, one]
			// [one, two] -> extra of x[s] - x[one]
			// l[i] = two

			// cerr << "> " << one << ' ' << l[i] << ' ' << two << endl;
			if (l[i] < one) { nl.push_back(l[i]); nr.push_back(one); ny.push_back(y[i]); }
			if (one < two && two <= r[i]) {
				// cerr << "extra: " << sz(nl) << ' ' << x[s] - x[one] << endl;
				extra[sz(nl)] += x[s] - x[one];
				nl.push_back(one); nr.push_back(two); ny.push_back(y[i]);
			}

			l[i] = two;
		}

		if (r[i] > g && l[i] <= g) {
			int one = g+1;
			while (one <= r[i] && h[one] < y[i]) one++;
			int two = g;
			while (two >= l[i] && h[two] < y[i]) two--;

			// [one, r]
			// [two, one] -> extra of x[one] - x[g]
			// r[i] = two

			if (one < r[i]) { nl.push_back(one); nr.push_back(r[i]); ny.push_back(y[i]); }
			if (two < one && two >= l[i]) {
				extra[sz(nl)] += x[one] - x[g];
				nl.push_back(two), nr.push_back(one), ny.push_back(y[i]);
			}

			r[i] = two;
		}

		if (l[i] < r[i]) {
			nl.push_back(l[i]);
			nr.push_back(r[i]);
			ny.push_back(y[i]);
		}
	}

	// cout << sz(l) << ' ' << sz(r) << ' ' << sz(y) << endl;
	swap(l, nl); swap(r, nr); swap(y, ny);
	// cout << sz(l) << ' ' << sz(r) << ' ' << sz(y) << endl;
	m = sz(l);
	// for (int i = 0; i < m; i++) {
	// 	cerr << l[i] << ' ' << r[i] << ' ' << y[i] << ' ' << extra[i] << endl;
	// }
	// s = 0;

	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;

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

				if (y[x] <= h[i]) {
					if (me != s.begin()) {
						auto it = prev(me);
						// cerr << "h2\n";
						add_edge(x, it->second, y[x] - it->first);
					}
				}
			}

			for (int x : ev[i]) if (on[x]) {
				auto me = s.find({y[x], x});
				if (y[x] <= h[i]) {
					auto it = next(me);
					if (it != s.end() && it->first <= h[i]) {
						// cerr << "h3\n";
						add_edge(x, it->second, it->first - y[x]);
					}
				}

				if (y[x] <= h[i]) {
					if (me != s.begin()) {
						// cerr << "h3\n";
						auto it = prev(me);
						add_edge(x, it->second, y[x] - it->first);
					}
				}

				s.erase(me);
			}

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

	build();
	int S = m;
	for (int i = 0; i < m; i++) {
		// cerr << "> " << l[i] << ' ' << s << ' ' << r[i] << ' ' << y[i] << ' ' << h[s] << endl;
		if (l[i] <= s && s <= r[i] && y[i] <= h[s]) {
			add_edge(S, i, y[i]);
		}
	}
	dijkstra(S);

	ll ans = INF;
	for (int i = 0; i < m; i++) {
		
		if (l[i] <= g && g <= r[i] && y[i] <= h[g]) {
			ans = min(ans, dist[i] + y[i]);
		}
	}
	// cerr << "base: " << ans << endl;

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 12 ms 19092 KB Output is correct
3 Incorrect 10 ms 19048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Incorrect 153 ms 42812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 29528 KB Output is correct
2 Correct 145 ms 42552 KB Output is correct
3 Correct 151 ms 43224 KB Output is correct
4 Correct 197 ms 45624 KB Output is correct
5 Correct 252 ms 48892 KB Output is correct
6 Correct 244 ms 47984 KB Output is correct
7 Correct 84 ms 33524 KB Output is correct
8 Correct 113 ms 35092 KB Output is correct
9 Correct 206 ms 48804 KB Output is correct
10 Correct 162 ms 42716 KB Output is correct
11 Correct 18 ms 19768 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 29528 KB Output is correct
2 Correct 145 ms 42552 KB Output is correct
3 Correct 151 ms 43224 KB Output is correct
4 Correct 197 ms 45624 KB Output is correct
5 Correct 252 ms 48892 KB Output is correct
6 Correct 244 ms 47984 KB Output is correct
7 Correct 84 ms 33524 KB Output is correct
8 Correct 113 ms 35092 KB Output is correct
9 Correct 206 ms 48804 KB Output is correct
10 Correct 162 ms 42716 KB Output is correct
11 Correct 18 ms 19768 KB Output is correct
12 Correct 165 ms 43240 KB Output is correct
13 Correct 168 ms 45604 KB Output is correct
14 Correct 274 ms 48980 KB Output is correct
15 Correct 171 ms 38480 KB Output is correct
16 Correct 175 ms 47408 KB Output is correct
17 Correct 180 ms 43068 KB Output is correct
18 Correct 145 ms 38376 KB Output is correct
19 Correct 171 ms 48288 KB Output is correct
20 Correct 108 ms 33968 KB Output is correct
21 Correct 28 ms 20912 KB Output is correct
22 Correct 135 ms 40624 KB Output is correct
23 Correct 129 ms 40468 KB Output is correct
24 Correct 102 ms 36760 KB Output is correct
25 Correct 111 ms 39320 KB Output is correct
26 Correct 93 ms 33776 KB Output is correct
27 Correct 248 ms 49232 KB Output is correct
28 Correct 138 ms 45476 KB Output is correct
29 Correct 224 ms 47912 KB Output is correct
30 Correct 88 ms 33428 KB Output is correct
31 Correct 226 ms 48792 KB Output is correct
32 Correct 125 ms 39424 KB Output is correct
33 Correct 116 ms 38552 KB Output is correct
34 Correct 135 ms 42668 KB Output is correct
35 Correct 121 ms 39412 KB Output is correct
36 Correct 105 ms 37840 KB Output is correct
37 Correct 96 ms 35512 KB Output is correct
38 Correct 95 ms 35116 KB Output is correct
39 Correct 143 ms 43800 KB Output is correct
40 Correct 101 ms 35912 KB Output is correct
41 Correct 96 ms 36700 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 12 ms 19092 KB Output is correct
3 Incorrect 10 ms 19048 KB Output isn't correct
4 Halted 0 ms 0 KB -