oj.uz

Submission #155086

# Submission time Handle Problem Language Result Execution time Memory
155086 2019-09-26T08:34:30 Z wakaka Sky Walking (IOI19_walk) C++14
43 / 100
 1805 ms 85432 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n = x.size();
	int m = l.size();
	vector<vector<int>> vert(n), hor(m);
	vector<vector<pair<int, int>>> events(n);
	for (int i = 0; i < m; ++i) {
		events[l[i]].emplace_back(i, 1);
		events[r[i]].emplace_back(i, -1);
	}
	auto f = [&](int q) {
		vector<pair<int, int>> lhs = {{h[q], q}}, rhs = {{h[q], q}};
		for (int i = q - 1; i >= 0; --i) {
			if (h[i] > lhs.back().first) lhs.push_back({h[i], i});
		}
		for (int i = q + 1; i < n; ++i) {
			if (h[i] > rhs.back().first) rhs.push_back({h[i], i});
		}
		for (int i = 0; i < m; ++i) {
			if (r[i] < q || l[i] > q) continue;
			auto it = lower_bound(lhs.begin(), lhs.end(), make_pair(y[i], -1));
			if (it == lhs.end()) continue;
			int p = it->second;
			if (x[p] < l[i]) continue;
			vert[p].push_back(y[i]);
			hor[i].push_back(x[p]);
		}
		for (int i = 0; i < m; ++i) {
			if (r[i] < q || l[i] > q) continue;
			auto it = lower_bound(rhs.begin(), rhs.end(), make_pair(y[i], -1));
			if (it == rhs.end()) continue;
			int p = it->second;
			if (x[p] > r[i]) continue;
			vert[p].push_back(y[i]);
			hor[i].push_back(x[p]);
		}
	};
	f(s);
	f(g);
	set<pair<int, int>> S;
	for (int i = 0; i < n; ++i) {
		for (auto& e : events[i]) {
			int j = e.first;
			vert[i].push_back(y[j]);
			hor[j].push_back(x[i]);
			if (e.second == 1) S.insert({y[j], j});
		}
		vector<int> nvert;
		for (int yj : vert[i]) {
			auto it = S.lower_bound({yj, -1});
			if (it == S.begin()) continue;
			int k = prev(it)->second;
			hor[k].push_back(x[i]);
			nvert.push_back(y[k]);
		}
		vert[i].insert(vert[i].end(), nvert.begin(), nvert.end());
		if (i == s || i == g) vert[i].push_back(0);
		for (auto& e : events[i]) {
			int j = e.first;
			if (e.second == -1) S.erase({y[j], j});
		}
	}
	map<pair<int, int>, int> mp;
	auto getId = [&](pair<int, int> a) {
		auto it = mp.find(a);
		if (it != mp.end()) return it->second;
		int s = mp.size();
		return mp[a] = s;
	};
	for (int i = 0; i < n; ++i)
		for (int j : vert[i]) getId({x[i], j});
	for (int i = 0; i < m; ++i)
		for (int j : hor[i]) getId({j, y[i]});
	vector<vector<pair<int, int>>> E(mp.size());
	for (int i = 0; i < n; ++i) {
		sort(vert[i].begin(), vert[i].end());
		vert[i].resize(unique(vert[i].begin(), vert[i].end()) - vert[i].begin());
		for (int j = 0; j + 1 < vert[i].size(); ++j) {
			int u = getId({x[i], vert[i][j]});
			int v = getId({x[i], vert[i][j + 1]});
			int d = vert[i][j + 1] - vert[i][j];
			E[u].push_back({v, d});
			E[v].push_back({u, d});
		}
	}
	for (int i = 0; i < m; ++i) {
		sort(hor[i].begin(), hor[i].end());
		hor[i].resize(unique(hor[i].begin(), hor[i].end()) - hor[i].begin());
		for (int j = 0; j + 1 < hor[i].size(); ++j) {
			int u = getId({hor[i][j], y[i]});
			int v = getId({hor[i][j + 1], y[i]});
			int d = hor[i][j + 1] - hor[i][j];
			E[u].push_back({v, d});
			E[v].push_back({u, d});
		}
	}
	const ll INF = 1LL << 60;
	vector<ll> dist(mp.size(), INF);
	int src = getId({x[s], 0}), dest = getId({x[g], 0});
	typedef pair<ll, int> Pair;
	priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
	dist[src] = 0;
	pq.emplace(dist[src], src);
	while (!pq.empty()) {
		int u = pq.top().second;
		ll cdist = pq.top().first;
		pq.pop();
		if (cdist > dist[u]) continue;
		for (auto e : E[u]) {
			int v = e.first;
			ll val = dist[u] + e.second;
			if (val < dist[v]) {
				dist[v] = val;
				pq.emplace(val, v);
			}
		}
	}
	return dist[dest] == INF ? -1 : dist[dest];
}

Compilation message

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:92:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vert[i].size(); ++j) {
                   ~~~~~~^~~~~~~~~~~~~~~~
walk.cpp:103:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < hor[i].size(); ++j) {
                   ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 356 KB Output is correct
17 Correct 2 ms 400 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 292 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 1102 ms 65100 KB Output is correct
4 Correct 1149 ms 72860 KB Output is correct
5 Correct 785 ms 56824 KB Output is correct
6 Correct 762 ms 54564 KB Output is correct
7 Correct 703 ms 57108 KB Output is correct
8 Correct 1376 ms 67504 KB Output is correct
9 Correct 879 ms 67948 KB Output is correct
10 Incorrect 1123 ms 73512 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 16248 KB Output is correct
2 Correct 1444 ms 73196 KB Output is correct
3 Correct 1434 ms 75532 KB Output is correct
4 Correct 1482 ms 84468 KB Output is correct
5 Correct 1685 ms 85432 KB Output is correct
6 Correct 1601 ms 82112 KB Output is correct
7 Correct 633 ms 48248 KB Output is correct
8 Correct 659 ms 49948 KB Output is correct
9 Correct 1687 ms 79900 KB Output is correct
10 Correct 910 ms 52836 KB Output is correct
11 Correct 18 ms 4344 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 16248 KB Output is correct
2 Correct 1444 ms 73196 KB Output is correct
3 Correct 1434 ms 75532 KB Output is correct
4 Correct 1482 ms 84468 KB Output is correct
5 Correct 1685 ms 85432 KB Output is correct
6 Correct 1601 ms 82112 KB Output is correct
7 Correct 633 ms 48248 KB Output is correct
8 Correct 659 ms 49948 KB Output is correct
9 Correct 1687 ms 79900 KB Output is correct
10 Correct 910 ms 52836 KB Output is correct
11 Correct 18 ms 4344 KB Output is correct
12 Correct 1491 ms 75568 KB Output is correct
13 Correct 1352 ms 83784 KB Output is correct
14 Correct 1805 ms 85196 KB Output is correct
15 Correct 1192 ms 73456 KB Output is correct
16 Correct 1127 ms 74100 KB Output is correct
17 Correct 1260 ms 83764 KB Output is correct
18 Correct 1117 ms 73512 KB Output is correct
19 Correct 1272 ms 72736 KB Output is correct
20 Correct 850 ms 45944 KB Output is correct
21 Correct 48 ms 9080 KB Output is correct
22 Correct 979 ms 67196 KB Output is correct
23 Correct 865 ms 65404 KB Output is correct
24 Correct 653 ms 52856 KB Output is correct
25 Correct 784 ms 60692 KB Output is correct
26 Correct 603 ms 45396 KB Output is correct
27 Correct 1782 ms 81768 KB Output is correct
28 Correct 1293 ms 78992 KB Output is correct
29 Correct 1787 ms 77824 KB Output is correct
30 Correct 610 ms 45148 KB Output is correct
31 Correct 1768 ms 75704 KB Output is correct
32 Correct 712 ms 47376 KB Output is correct
33 Correct 713 ms 47464 KB Output is correct
34 Correct 979 ms 53128 KB Output is correct
35 Correct 826 ms 54540 KB Output is correct
36 Correct 763 ms 49280 KB Output is correct
37 Correct 630 ms 45480 KB Output is correct
38 Correct 651 ms 47188 KB Output is correct
39 Correct 1299 ms 59676 KB Output is correct
40 Correct 755 ms 48304 KB Output is correct
41 Correct 573 ms 47920 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 356 KB Output is correct
17 Correct 2 ms 400 KB Output is correct
18 Correct 2 ms 292 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 1102 ms 65100 KB Output is correct
21 Correct 1149 ms 72860 KB Output is correct
22 Correct 785 ms 56824 KB Output is correct
23 Correct 762 ms 54564 KB Output is correct
24 Correct 703 ms 57108 KB Output is correct
25 Correct 1376 ms 67504 KB Output is correct
26 Correct 879 ms 67948 KB Output is correct
27 Incorrect 1123 ms 73512 KB Output isn't correct
28 Halted 0 ms 0 KB -