oj.uz

Submission #807524

# Submission time Handle Problem Language Result Execution time Memory
807524 2023-08-04T18:58:35 Z faruk Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 779316 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

vector<vector<pii> > graph;
vector<map<ll, ll> > idxs; // for each i , idxs[i][a] is index of node at that llersection
vector<ll> x;
ll n;

ll get_idx_at_height(ll a, ll h) {
	ll my_node = idxs[a][h];
	if (my_node == 0)
	{
		my_node = graph.size(), idxs[a][h] = my_node;
		graph.push_back(vector<pii>());
	}
	return my_node;
}

void add_edge(ll a, vector<ll> nei, ll h) {
	ll my_node = get_idx_at_height(a, h);
	for (ll b : nei) {
		ll idx = get_idx_at_height(b, h);
		graph[idx].push_back(mp((ll)my_node, (ll)abs(x[a] - x[b])));
		graph[my_node].push_back(mp((ll)idx, (ll)abs(x[a] - x[b])));
	}
}

struct bridge {
	ll l, r, h;
	bridge() {}
	bridge(ll L, ll R,ll H) {l = L, r = R, h = H;}
};

bool cmp(bridge a, bridge b) {return a.h > b.h;}

struct tower {
	ll idx, h, x;
	tower() {}
	tower(ll L,ll H, ll X) {idx = L, h = H, x=X;}
};

bool cmp2(tower a, tower b) {return a.h > b.h;}

ll dijkstra(ll a, ll b) {
	priority_queue<pii, vector<pii>, greater<pii>> q;
	q.push({0, a});
	vector<ll> dist(graph.size(), 1e18);
	dist[a] = 0;
	while (!q.empty()) {
		pii curr = q.top(); q.pop();
		if (curr.first > dist[curr.second])
			continue;
		for (pii O : graph[curr.second]) {
			ll t = O.first;
			ll w = O.second;
			if (dist[t] > curr.first + w) {
				dist[t] = curr.first + w;
				q.push({dist[t], t});
			}
		}
	}
	if (dist[b] == 1e18)
		return -1;
	return dist[b];
}

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) {
	::x = vector<ll>(x.begin(), x.end());
	n = x.size();
	graph.resize(n);
	idxs.resize(n);
	vector<tower> towersort(n);
	for (ll i = 0; i < n; i++)
	 	towersort[i] = tower(i, h[i], x[i]);
	sort(all(towersort), cmp2);
	ll m = l.size();
	vector<bridge> bridges(m);
	for (ll i = 0; i < m; i++)
		bridges[i] = bridge(l[i], r[i], y[i]);
	sort(all(bridges), cmp);

	ll pnt = 0;
	set<ll> xs;
	for (auto bridge : bridges) {
		while (pnt < n and towersort[pnt].h >= bridge.h)
			xs.insert(towersort[pnt++].idx);
		auto lowest = xs.lower_bound(bridge.l);
		auto highest = xs.upper_bound(bridge.r);
		auto prev = lowest;
		for (; lowest != highest; lowest = next(lowest)) {
			vector<ll> nei;
			if (prev != lowest)
				nei.push_back(*prev);
			if (next(lowest) != highest)
				nei.push_back(*next(lowest));
			
			add_edge(*lowest, nei, bridge.h);
			prev = lowest;
		}
	}

	for (ll i = 0; i < n; i++) {
		map<ll, ll> hghts = idxs[i];
		pii prev = {0, i};
		for (pii a : hghts) {
			graph[prev.second].push_back(mp(a.second, abs(a.first - prev.first)));
			graph[a.second].push_back(mp(prev.second, abs(a.first - prev.first)));
			prev = a;
		}
	}

	return dijkstra(s, g);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 468 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1225 ms 191604 KB Output is correct
4 Correct 1032 ms 207128 KB Output is correct
5 Correct 732 ms 182188 KB Output is correct
6 Correct 674 ms 158320 KB Output is correct
7 Correct 713 ms 182252 KB Output is correct
8 Correct 1785 ms 255652 KB Output is correct
9 Correct 847 ms 174304 KB Output is correct
10 Correct 1520 ms 303196 KB Output is correct
11 Correct 559 ms 88816 KB Output is correct
12 Correct 313 ms 63312 KB Output is correct
13 Correct 1249 ms 261412 KB Output is correct
14 Correct 281 ms 62536 KB Output is correct
15 Correct 291 ms 64380 KB Output is correct
16 Correct 299 ms 64276 KB Output is correct
17 Correct 257 ms 61904 KB Output is correct
18 Correct 220 ms 60512 KB Output is correct
19 Correct 8 ms 3540 KB Output is correct
20 Correct 105 ms 31952 KB Output is correct
21 Correct 262 ms 57912 KB Output is correct
22 Correct 273 ms 62764 KB Output is correct
23 Correct 329 ms 80272 KB Output is correct
24 Correct 317 ms 62684 KB Output is correct
25 Correct 269 ms 61020 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 21084 KB Output is correct
2 Execution timed out 4059 ms 779316 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 21084 KB Output is correct
2 Execution timed out 4059 ms 779316 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1225 ms 191604 KB Output is correct
21 Correct 1032 ms 207128 KB Output is correct
22 Correct 732 ms 182188 KB Output is correct
23 Correct 674 ms 158320 KB Output is correct
24 Correct 713 ms 182252 KB Output is correct
25 Correct 1785 ms 255652 KB Output is correct
26 Correct 847 ms 174304 KB Output is correct
27 Correct 1520 ms 303196 KB Output is correct
28 Correct 559 ms 88816 KB Output is correct
29 Correct 313 ms 63312 KB Output is correct
30 Correct 1249 ms 261412 KB Output is correct
31 Correct 281 ms 62536 KB Output is correct
32 Correct 291 ms 64380 KB Output is correct
33 Correct 299 ms 64276 KB Output is correct
34 Correct 257 ms 61904 KB Output is correct
35 Correct 220 ms 60512 KB Output is correct
36 Correct 8 ms 3540 KB Output is correct
37 Correct 105 ms 31952 KB Output is correct
38 Correct 262 ms 57912 KB Output is correct
39 Correct 273 ms 62764 KB Output is correct
40 Correct 329 ms 80272 KB Output is correct
41 Correct 317 ms 62684 KB Output is correct
42 Correct 269 ms 61020 KB Output is correct
43 Correct 72 ms 21084 KB Output is correct
44 Execution timed out 4059 ms 779316 KB Time limit exceeded
45 Halted 0 ms 0 KB -