oj.uz

Submission #155084

# Submission time Handle Problem Language Result Execution time Memory
155084 2019-09-26T08:20:54 Z wakaka Sky Walking (IOI19_walk) C++14
43 / 100
 1882 ms 86068 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 cmp = [&](int a, int b) {
		if (y[a] != y[b]) return y[a] < y[b];
		return a < b;
	};
	set<int, decltype(cmp)> S(cmp);
	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(j);
		}
		for (auto& e : events[i]) {
			int j = e.first;
			auto it = S.lower_bound(j);
			if (it == S.begin()) continue;
			int k = *prev(it);
			hor[k].push_back(x[i]);
			vert[i].push_back(y[k]);
		}
		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(j);
		}
	}
	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);
	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:95:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vert[i].size(); ++j) {
                   ~~~~~~^~~~~~~~~~~~~~~~
walk.cpp:106: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 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 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 380 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 256 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 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 380 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 476 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 1125 ms 65792 KB Output is correct
4 Correct 1028 ms 73884 KB Output is correct
5 Correct 656 ms 57556 KB Output is correct
6 Correct 726 ms 55232 KB Output is correct
7 Correct 707 ms 57536 KB Output is correct
8 Correct 1219 ms 68152 KB Output is correct
9 Correct 906 ms 68772 KB Output is correct
10 Incorrect 1201 ms 74628 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 233 ms 16476 KB Output is correct
2 Correct 1531 ms 73556 KB Output is correct
3 Correct 1484 ms 76160 KB Output is correct
4 Correct 1570 ms 83912 KB Output is correct
5 Correct 1749 ms 85228 KB Output is correct
6 Correct 1641 ms 81000 KB Output is correct
7 Correct 642 ms 48384 KB Output is correct
8 Correct 642 ms 49040 KB Output is correct
9 Correct 1882 ms 78444 KB Output is correct
10 Correct 911 ms 52480 KB Output is correct
11 Correct 18 ms 4216 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 16476 KB Output is correct
2 Correct 1531 ms 73556 KB Output is correct
3 Correct 1484 ms 76160 KB Output is correct
4 Correct 1570 ms 83912 KB Output is correct
5 Correct 1749 ms 85228 KB Output is correct
6 Correct 1641 ms 81000 KB Output is correct
7 Correct 642 ms 48384 KB Output is correct
8 Correct 642 ms 49040 KB Output is correct
9 Correct 1882 ms 78444 KB Output is correct
10 Correct 911 ms 52480 KB Output is correct
11 Correct 18 ms 4216 KB Output is correct
12 Correct 1647 ms 76140 KB Output is correct
13 Correct 1432 ms 83448 KB Output is correct
14 Correct 1714 ms 84932 KB Output is correct
15 Correct 1293 ms 73072 KB Output is correct
16 Correct 1174 ms 73560 KB Output is correct
17 Correct 1243 ms 83240 KB Output is correct
18 Correct 1148 ms 73032 KB Output is correct
19 Correct 1213 ms 73532 KB Output is correct
20 Correct 766 ms 47076 KB Output is correct
21 Correct 48 ms 9200 KB Output is correct
22 Correct 1012 ms 69468 KB Output is correct
23 Correct 909 ms 67792 KB Output is correct
24 Correct 699 ms 55072 KB Output is correct
25 Correct 798 ms 62824 KB Output is correct
26 Correct 606 ms 47756 KB Output is correct
27 Correct 1787 ms 86068 KB Output is correct
28 Correct 1297 ms 83728 KB Output is correct
29 Correct 1676 ms 81684 KB Output is correct
30 Correct 649 ms 48140 KB Output is correct
31 Correct 1734 ms 79156 KB Output is correct
32 Correct 727 ms 50956 KB Output is correct
33 Correct 731 ms 50728 KB Output is correct
34 Correct 966 ms 56316 KB Output is correct
35 Correct 813 ms 57796 KB Output is correct
36 Correct 649 ms 52704 KB Output is correct
37 Correct 561 ms 49016 KB Output is correct
38 Correct 656 ms 48964 KB Output is correct
39 Correct 1205 ms 60828 KB Output is correct
40 Correct 622 ms 50268 KB Output is correct
41 Correct 690 ms 49656 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 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 380 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 256 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 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 380 KB Output is correct
18 Correct 2 ms 476 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 1125 ms 65792 KB Output is correct
21 Correct 1028 ms 73884 KB Output is correct
22 Correct 656 ms 57556 KB Output is correct
23 Correct 726 ms 55232 KB Output is correct
24 Correct 707 ms 57536 KB Output is correct
25 Correct 1219 ms 68152 KB Output is correct
26 Correct 906 ms 68772 KB Output is correct
27 Incorrect 1201 ms 74628 KB Output isn't correct
28 Halted 0 ms 0 KB -