oj.uz

Submission #390939

# Submission time Handle Problem Language Result Execution time Memory
390939 2021-04-17T12:22:33 Z SuhaibSawalha1 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 946656 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)2e7), 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);
	}
	set<array<int, 2>> s;
	for (int i = 0; i < n; ++i) {
		for (int v : S[i]) {
			s.insert({y[v], v});
		}
		for (auto &v : s) {
			if (v[0] > h[i]) {
				break;
			}
			add(i);
			add(n + v[1]);
			p.push_back({x[i], v[0]});
		}
		for (int v : E[i]) {
			s.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 394 ms 626448 KB Output is correct
2 Correct 371 ms 626516 KB Output is correct
3 Correct 368 ms 626488 KB Output is correct
4 Correct 366 ms 626536 KB Output is correct
5 Correct 382 ms 626532 KB Output is correct
6 Correct 371 ms 626636 KB Output is correct
7 Correct 367 ms 626492 KB Output is correct
8 Correct 368 ms 626488 KB Output is correct
9 Correct 368 ms 626456 KB Output is correct
10 Correct 370 ms 626500 KB Output is correct
11 Correct 374 ms 626460 KB Output is correct
12 Correct 371 ms 626500 KB Output is correct
13 Correct 363 ms 626500 KB Output is correct
14 Correct 374 ms 626432 KB Output is correct
15 Correct 368 ms 626500 KB Output is correct
16 Correct 362 ms 626528 KB Output is correct
17 Correct 362 ms 626568 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 626500 KB Output is correct
2 Correct 372 ms 626500 KB Output is correct
3 Correct 3865 ms 697932 KB Output is correct
4 Correct 1349 ms 702452 KB Output is correct
5 Correct 801 ms 694696 KB Output is correct
6 Correct 794 ms 690912 KB Output is correct
7 Correct 796 ms 694908 KB Output is correct
8 Execution timed out 4106 ms 727476 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 642592 KB Output is correct
2 Execution timed out 4129 ms 946656 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 642592 KB Output is correct
2 Execution timed out 4129 ms 946656 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 626448 KB Output is correct
2 Correct 371 ms 626516 KB Output is correct
3 Correct 368 ms 626488 KB Output is correct
4 Correct 366 ms 626536 KB Output is correct
5 Correct 382 ms 626532 KB Output is correct
6 Correct 371 ms 626636 KB Output is correct
7 Correct 367 ms 626492 KB Output is correct
8 Correct 368 ms 626488 KB Output is correct
9 Correct 368 ms 626456 KB Output is correct
10 Correct 370 ms 626500 KB Output is correct
11 Correct 374 ms 626460 KB Output is correct
12 Correct 371 ms 626500 KB Output is correct
13 Correct 363 ms 626500 KB Output is correct
14 Correct 374 ms 626432 KB Output is correct
15 Correct 368 ms 626500 KB Output is correct
16 Correct 362 ms 626528 KB Output is correct
17 Correct 362 ms 626568 KB Output is correct
18 Correct 363 ms 626500 KB Output is correct
19 Correct 372 ms 626500 KB Output is correct
20 Correct 3865 ms 697932 KB Output is correct
21 Correct 1349 ms 702452 KB Output is correct
22 Correct 801 ms 694696 KB Output is correct
23 Correct 794 ms 690912 KB Output is correct
24 Correct 796 ms 694908 KB Output is correct
25 Execution timed out 4106 ms 727476 KB Time limit exceeded
26 Halted 0 ms 0 KB -