oj.uz

Submission #417249

# Submission time Handle Problem Language Result Execution time Memory
417249 2021-06-03T13:58:22 Z Mlxa Sky Walking (IOI19_walk) C++14
0 / 100
 2259 ms 435456 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);
			}
		}
	}
	return dst[to];
}

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 78532 KB Output is correct
2 Correct 40 ms 78532 KB Output is correct
3 Correct 41 ms 78544 KB Output is correct
4 Incorrect 40 ms 78564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 78448 KB Output is correct
2 Correct 41 ms 78540 KB Output is correct
3 Correct 1866 ms 211164 KB Output is correct
4 Correct 1577 ms 221392 KB Output is correct
5 Correct 1193 ms 201904 KB Output is correct
6 Correct 2259 ms 187196 KB Output is correct
7 Incorrect 1173 ms 202060 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 91732 KB Output is correct
2 Runtime error 1579 ms 435456 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 181 ms 91732 KB Output is correct
2 Runtime error 1579 ms 435456 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 41 ms 78532 KB Output is correct
2 Correct 40 ms 78532 KB Output is correct
3 Correct 41 ms 78544 KB Output is correct
4 Incorrect 40 ms 78564 KB Output isn't correct
5 Halted 0 ms 0 KB -