oj.uz

Submission #417274

# Submission time Handle Problem Language Result Execution time Memory
417274 2021-06-03T14:14:57 Z Mlxa Sky Walking (IOI19_walk) C++14
0 / 100
 654 ms 370436 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 = 2e6 + 10;

int ff = 0;
vector<pair<int, int>> g[N];
vector<pair<int, 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<int, int>;
const int INF = INT_MAX;
priority_queue<T, vector<T>, greater<T>> q;
int dst[N];
int ground[N];

bool wastl = false;
int iter = 0;
bool istl() {
	if (wastl) {
		return true;
	}
	++iter;
	if (iter & 1023) {
		return false;
	}
	return wastl = clock() > 3.95L * CLOCKS_PER_SEC;
}
}

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 = -1, lv = -1;
		for (int j = l[i]; j <= r[i]; ++j) {
			if (h[j] < y[i]) {
				continue;
			}
			int v = ff++;
			ys[j].emplace_back(y[i], v);
			if (lst != -1) {
				edge(v, lv, abs(x[lst] - x[j]));
			}
			lst = j;
			lv = v;
		}
	}
	for (int i = 0; i < (int)x.size(); ++i) {
		ground[i] = ff++;
		sort(all(ys[i]));
		int ly = 0, lv = ground[i];
		for (auto cur : ys[i]) {
			edge(cur.y, lv, abs(cur.x - ly));
			tie(ly, lv) = cur;
		}
	}

	int from = ground[st], to = ground[fi];
	fill_n(dst, N, INF);
	dst[from] = 0;
	q.emplace(dst[from], from);
	while (q.size() && !istl()) {
		int d, w;
		int v, u;
		tie(d, v) = q.top(); q.pop();
		if (d != dst[v]) {
			continue;
		}
		if (v == to) {
			break;
		}
		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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 102028 KB Output is correct
2 Correct 55 ms 101956 KB Output is correct
3 Correct 56 ms 101952 KB Output is correct
4 Correct 57 ms 102036 KB Output is correct
5 Correct 55 ms 101984 KB Output is correct
6 Incorrect 62 ms 102088 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 101996 KB Output is correct
2 Correct 65 ms 102004 KB Output is correct
3 Correct 445 ms 148932 KB Output is correct
4 Incorrect 654 ms 154608 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 110788 KB Output is correct
2 Runtime error 472 ms 370436 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 140 ms 110788 KB Output is correct
2 Runtime error 472 ms 370436 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 56 ms 102028 KB Output is correct
2 Correct 55 ms 101956 KB Output is correct
3 Correct 56 ms 101952 KB Output is correct
4 Correct 57 ms 102036 KB Output is correct
5 Correct 55 ms 101984 KB Output is correct
6 Incorrect 62 ms 102088 KB Output isn't correct
7 Halted 0 ms 0 KB -