oj.uz

Submission #390930

# Submission time Handle Problem Language Result Execution time Memory
390930 2021-04-17T12:05:15 Z SuhaibSawalha1 Sky Walking (IOI19_walk) C++17
10 / 100
 3606 ms 195236 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

int dist (array<int, 2> &a, array<int, 2> &b) {
	return abs(a[0] - b[0]) + abs(a[1] - b[1]);
}

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 src, int snk) {
	vector<array<int, 2>> p;
	int n = x.size(), m = y.size();
	vector<vector<int>> seg(n + m), adj((int)1e6), S(n), E(n);
	auto add = [&] (int i) {
		adj[p.size()].push_back(i);
		seg[i].push_back(p.size());
	};
	for (int i = 0; i < n; ++i) {
		add(i);
		p.push_back({x[i], 0});
		add(i);
		p.push_back({x[i], h[i]});
	}
	for (int i = 0; i < m; ++i) {
		add(l[i]);
		add(n + i);
		p.push_back({x[l[i]], y[i]});
		add(r[i]);
		add(n + i);
		p.push_back({x[r[i]], y[i]});
		S[l[i]].push_back(i);
		E[r[i]].push_back(i);
	}
	multiset<array<int, 2>> ms;
	for (int i = 0; i < n; ++i) {
		for (int v : S[i]) {
			ms.insert({y[v], v});
		}
		for (auto &v : ms) {
			if (v[0] > h[i]) {
				break;
			}
			add(i);
			add(n + v[1]);
			p.push_back({x[i], v[0]});
		}
		for (int v : E[i]) {
			ms.erase({y[v], v});
		}
	}
	priority_queue<pair<long long, int>> pq;
	pq.push({0, 2 * src});
	vector<long long> dis(adj.size(), 1e18);
	dis[2 * src] = 0;
	while (pq.size()) {
		long long d = -pq.top().first;
		int u = pq.top().second;
		pq.pop();
		if (d != dis[u]) {
			continue;
		}
		for (int e : adj[u]) {
			for (int v : seg[e]) {
				int dd = dist(p[u], p[v]);
				if (d + dd < dis[v]) {
					dis[v] = d + dd;
					pq.push({-dis[v], v});
				}
			}
		}
	}
	return dis[2 * snk] == 1e18 ? -1 : dis[2 * snk];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31516 KB Output is correct
2 Correct 23 ms 31564 KB Output is correct
3 Correct 20 ms 31564 KB Output is correct
4 Correct 20 ms 31564 KB Output is correct
5 Correct 20 ms 31564 KB Output is correct
6 Correct 20 ms 31624 KB Output is correct
7 Correct 21 ms 31648 KB Output is correct
8 Correct 21 ms 31616 KB Output is correct
9 Correct 21 ms 31564 KB Output is correct
10 Correct 21 ms 31692 KB Output is correct
11 Correct 21 ms 31564 KB Output is correct
12 Correct 20 ms 31564 KB Output is correct
13 Correct 20 ms 31600 KB Output is correct
14 Correct 20 ms 31564 KB Output is correct
15 Correct 20 ms 31620 KB Output is correct
16 Correct 19 ms 31564 KB Output is correct
17 Correct 20 ms 31692 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31564 KB Output is correct
2 Correct 20 ms 31540 KB Output is correct
3 Correct 3606 ms 102836 KB Output is correct
4 Runtime error 457 ms 195236 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 47656 KB Output is correct
2 Runtime error 407 ms 165032 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 47656 KB Output is correct
2 Runtime error 407 ms 165032 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31516 KB Output is correct
2 Correct 23 ms 31564 KB Output is correct
3 Correct 20 ms 31564 KB Output is correct
4 Correct 20 ms 31564 KB Output is correct
5 Correct 20 ms 31564 KB Output is correct
6 Correct 20 ms 31624 KB Output is correct
7 Correct 21 ms 31648 KB Output is correct
8 Correct 21 ms 31616 KB Output is correct
9 Correct 21 ms 31564 KB Output is correct
10 Correct 21 ms 31692 KB Output is correct
11 Correct 21 ms 31564 KB Output is correct
12 Correct 20 ms 31564 KB Output is correct
13 Correct 20 ms 31600 KB Output is correct
14 Correct 20 ms 31564 KB Output is correct
15 Correct 20 ms 31620 KB Output is correct
16 Correct 19 ms 31564 KB Output is correct
17 Correct 20 ms 31692 KB Output is correct
18 Correct 20 ms 31564 KB Output is correct
19 Correct 20 ms 31540 KB Output is correct
20 Correct 3606 ms 102836 KB Output is correct
21 Runtime error 457 ms 195236 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -