oj.uz

Submission #807517

# Submission time Handle Problem Language Result Execution time Memory
807517 2023-08-04T18:47:51 Z faruk Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 704444 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<int, int> > idxs; // for each i , idxs[i][a] is index of node at that intersection
vector<int> x;
int n;

int get_idx_at_height(int a, int h) {
	int 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(int a, vector<int> nei, int h) {
	int my_node = get_idx_at_height(a, h);
	for (int b : nei) {
		int 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 {
	int l, r, h;
	bridge() {}
	bridge(int L, int R,int H) {l = L, r = R, h = H;}
};

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

struct tower {
	int idx, h, x;
	tower() {}
	tower(int L,int H, int 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 (auto &[t, w] : graph[curr.second]) {
			if (dist[t] > curr.first + w) {
				dist[t] = curr.first + w;
				q.push({dist[t], t});
			}
		}
	}
	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 = x;
	n = x.size();
	graph.resize(n);
	idxs.resize(n);
	vector<tower> towersort(n);
	for (int i = 0; i < n; i++)
	 	towersort[i] = tower(i, h[i], x[i]);
	sort(all(towersort), cmp2);
	int m = l.size();
	vector<bridge> bridges(m);
	for (int i = 0; i < m; i++)
		bridges[i] = bridge(l[i], r[i], y[i]);
	sort(all(bridges), cmp);

	int pnt = 0;
	set<int> 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<int> 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 (int i = 0; i < n; i++) {
		map<int, int> 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
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1049 ms 179744 KB Output is correct
4 Correct 979 ms 194172 KB Output is correct
5 Correct 638 ms 171204 KB Output is correct
6 Correct 552 ms 148408 KB Output is correct
7 Incorrect 629 ms 171188 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 18768 KB Output is correct
2 Execution timed out 4070 ms 704444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 18768 KB Output is correct
2 Execution timed out 4070 ms 704444 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 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -