oj.uz

Submission #417257

# Submission time Handle Problem Language Result Execution time Memory
417257 2021-06-03T14:02:24 Z Mlxa Sky Walking (IOI19_walk) C++14
10 / 100
 2651 ms 437808 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "walk.h"

namespace my {
const int N = 1e6 + 10;
map<pair<int, int>, int> was;

int id(int x, int y) {
	auto p = mp(x, y);
	if (was.count(p)) {
		return was[p];
	} else {
		int v = (int)was.size();
		assert(v < N);
		return was[p] = v;
	}
}

vector<pair<int, int>> g[N];
set<int> ys[N];

void edge(int v, int u, int w) {
	g[v].emplace_back(u, w);
	g[u].emplace_back(v, w);
}

using T = pair<ll, int>;
const ll INF = 1e18;
priority_queue<T, vector<T>, greater<T>> q;
ll dst[N];
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int st, int fi) {
	using namespace my;
	for (int i = 0; i < (int)y.size(); ++i) {
		int lst = l[i];
		for (int j = l[i] + 1; j <= r[i]; ++j) {
			if (h[j] < y[i]) {
				continue;
			}
			edge(id(x[lst], y[i]), id(x[j], y[i]), abs(x[lst] - x[j]));
			lst = j;
		}
		for (int j = l[i]; j <= r[i]; ++j) {
			if (h[j] >= y[i]) {
				ys[j].insert(y[i]);
			}
		}
	}
	for (int i = 0; i < (int)x.size(); ++i) {
		int ly = 0, lv = id(x[i], 0);
		for (int cur : ys[i]) {
			int ver = id(x[i], cur);
			edge(lv, ver, abs(cur - ly));
			ly = cur, lv = ver;
		}
	}

	int from = id(x[st], 0), to = id(x[fi], 0);
	fill_n(dst, N, INF);
	dst[from] = 0;
	q.emplace(dst[from], from);
	while (q.size()) {
		ll d, w;
		int v, u;
		tie(d, v) = q.top(); q.pop();
		if (d != dst[v]) {
			continue;
		}
		for (auto e : g[v]) {
			u = e.x, w = e.y;
			if (dst[u] > dst[v] + w) {
				dst[u] = dst[v] + w;
				q.emplace(dst[u], u);
			}
		}
	}
	if (dst[to] > INF / 2) {
		return -1;
	}
	return dst[to];
}

#ifdef LC
#include "grader.cpp"
#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 78568 KB Output is correct
2 Correct 48 ms 78556 KB Output is correct
3 Correct 45 ms 78468 KB Output is correct
4 Correct 45 ms 78496 KB Output is correct
5 Correct 47 ms 78688 KB Output is correct
6 Correct 45 ms 78676 KB Output is correct
7 Correct 63 ms 78664 KB Output is correct
8 Correct 48 ms 78532 KB Output is correct
9 Correct 54 ms 78480 KB Output is correct
10 Correct 50 ms 78628 KB Output is correct
11 Correct 46 ms 78520 KB Output is correct
12 Correct 57 ms 78500 KB Output is correct
13 Correct 52 ms 78564 KB Output is correct
14 Correct 47 ms 78540 KB Output is correct
15 Correct 46 ms 78472 KB Output is correct
16 Correct 47 ms 78564 KB Output is correct
17 Correct 47 ms 78708 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 78544 KB Output is correct
2 Correct 51 ms 78480 KB Output is correct
3 Correct 2221 ms 209320 KB Output is correct
4 Correct 1617 ms 218872 KB Output is correct
5 Correct 1222 ms 199572 KB Output is correct
6 Correct 2395 ms 184616 KB Output is correct
7 Correct 1236 ms 199580 KB Output is correct
8 Correct 2651 ms 247568 KB Output is correct
9 Correct 1370 ms 197848 KB Output is correct
10 Runtime error 1555 ms 437808 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 91752 KB Output is correct
2 Runtime error 1700 ms 434564 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 91752 KB Output is correct
2 Runtime error 1700 ms 434564 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 78568 KB Output is correct
2 Correct 48 ms 78556 KB Output is correct
3 Correct 45 ms 78468 KB Output is correct
4 Correct 45 ms 78496 KB Output is correct
5 Correct 47 ms 78688 KB Output is correct
6 Correct 45 ms 78676 KB Output is correct
7 Correct 63 ms 78664 KB Output is correct
8 Correct 48 ms 78532 KB Output is correct
9 Correct 54 ms 78480 KB Output is correct
10 Correct 50 ms 78628 KB Output is correct
11 Correct 46 ms 78520 KB Output is correct
12 Correct 57 ms 78500 KB Output is correct
13 Correct 52 ms 78564 KB Output is correct
14 Correct 47 ms 78540 KB Output is correct
15 Correct 46 ms 78472 KB Output is correct
16 Correct 47 ms 78564 KB Output is correct
17 Correct 47 ms 78708 KB Output is correct
18 Correct 65 ms 78544 KB Output is correct
19 Correct 51 ms 78480 KB Output is correct
20 Correct 2221 ms 209320 KB Output is correct
21 Correct 1617 ms 218872 KB Output is correct
22 Correct 1222 ms 199572 KB Output is correct
23 Correct 2395 ms 184616 KB Output is correct
24 Correct 1236 ms 199580 KB Output is correct
25 Correct 2651 ms 247568 KB Output is correct
26 Correct 1370 ms 197848 KB Output is correct
27 Runtime error 1555 ms 437808 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -