oj.uz

Submission #155087

# Submission time Handle Problem Language Result Execution time Memory
155087 2019-09-26T08:37:52 Z wakaka Sky Walking (IOI19_walk) C++14
100 / 100
 3145 ms 121812 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 (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 (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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 1 ms 452 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 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 1098 ms 64548 KB Output is correct
4 Correct 987 ms 71928 KB Output is correct
5 Correct 664 ms 55544 KB Output is correct
6 Correct 698 ms 53704 KB Output is correct
7 Correct 660 ms 55800 KB Output is correct
8 Correct 1230 ms 67044 KB Output is correct
9 Correct 926 ms 66704 KB Output is correct
10 Correct 1087 ms 72412 KB Output is correct
11 Correct 845 ms 58760 KB Output is correct
12 Correct 673 ms 49912 KB Output is correct
13 Correct 1038 ms 76128 KB Output is correct
14 Correct 797 ms 50884 KB Output is correct
15 Correct 927 ms 50136 KB Output is correct
16 Correct 706 ms 51664 KB Output is correct
17 Correct 629 ms 49144 KB Output is correct
18 Correct 1700 ms 61820 KB Output is correct
19 Correct 19 ms 2808 KB Output is correct
20 Correct 264 ms 25468 KB Output is correct
21 Correct 558 ms 48284 KB Output is correct
22 Correct 656 ms 48900 KB Output is correct
23 Correct 1409 ms 61420 KB Output is correct
24 Correct 645 ms 50240 KB Output is correct
25 Correct 576 ms 49252 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 16256 KB Output is correct
2 Correct 1473 ms 73272 KB Output is correct
3 Correct 1477 ms 75184 KB Output is correct
4 Correct 1522 ms 82208 KB Output is correct
5 Correct 1691 ms 83384 KB Output is correct
6 Correct 1660 ms 80652 KB Output is correct
7 Correct 640 ms 47320 KB Output is correct
8 Correct 652 ms 47620 KB Output is correct
9 Correct 1846 ms 79368 KB Output is correct
10 Correct 915 ms 51176 KB Output is correct
11 Correct 19 ms 4344 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 16256 KB Output is correct
2 Correct 1473 ms 73272 KB Output is correct
3 Correct 1477 ms 75184 KB Output is correct
4 Correct 1522 ms 82208 KB Output is correct
5 Correct 1691 ms 83384 KB Output is correct
6 Correct 1660 ms 80652 KB Output is correct
7 Correct 640 ms 47320 KB Output is correct
8 Correct 652 ms 47620 KB Output is correct
9 Correct 1846 ms 79368 KB Output is correct
10 Correct 915 ms 51176 KB Output is correct
11 Correct 19 ms 4344 KB Output is correct
12 Correct 1531 ms 75152 KB Output is correct
13 Correct 1377 ms 81664 KB Output is correct
14 Correct 1723 ms 83312 KB Output is correct
15 Correct 1089 ms 71480 KB Output is correct
16 Correct 1124 ms 72072 KB Output is correct
17 Correct 1250 ms 81768 KB Output is correct
18 Correct 1175 ms 71756 KB Output is correct
19 Correct 1190 ms 73556 KB Output is correct
20 Correct 705 ms 46956 KB Output is correct
21 Correct 50 ms 9336 KB Output is correct
22 Correct 978 ms 69212 KB Output is correct
23 Correct 894 ms 67220 KB Output is correct
24 Correct 679 ms 54648 KB Output is correct
25 Correct 750 ms 62584 KB Output is correct
26 Correct 565 ms 47224 KB Output is correct
27 Correct 1692 ms 83736 KB Output is correct
28 Correct 1273 ms 81120 KB Output is correct
29 Correct 1660 ms 80476 KB Output is correct
30 Correct 641 ms 47072 KB Output is correct
31 Correct 2262 ms 79344 KB Output is correct
32 Correct 780 ms 49308 KB Output is correct
33 Correct 800 ms 49316 KB Output is correct
34 Correct 1046 ms 54964 KB Output is correct
35 Correct 816 ms 56460 KB Output is correct
36 Correct 742 ms 51204 KB Output is correct
37 Correct 563 ms 47516 KB Output is correct
38 Correct 674 ms 47104 KB Output is correct
39 Correct 1480 ms 59888 KB Output is correct
40 Correct 642 ms 48628 KB Output is correct
41 Correct 568 ms 47864 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 1 ms 452 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 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 1098 ms 64548 KB Output is correct
21 Correct 987 ms 71928 KB Output is correct
22 Correct 664 ms 55544 KB Output is correct
23 Correct 698 ms 53704 KB Output is correct
24 Correct 660 ms 55800 KB Output is correct
25 Correct 1230 ms 67044 KB Output is correct
26 Correct 926 ms 66704 KB Output is correct
27 Correct 1087 ms 72412 KB Output is correct
28 Correct 845 ms 58760 KB Output is correct
29 Correct 673 ms 49912 KB Output is correct
30 Correct 1038 ms 76128 KB Output is correct
31 Correct 797 ms 50884 KB Output is correct
32 Correct 927 ms 50136 KB Output is correct
33 Correct 706 ms 51664 KB Output is correct
34 Correct 629 ms 49144 KB Output is correct
35 Correct 1700 ms 61820 KB Output is correct
36 Correct 19 ms 2808 KB Output is correct
37 Correct 264 ms 25468 KB Output is correct
38 Correct 558 ms 48284 KB Output is correct
39 Correct 656 ms 48900 KB Output is correct
40 Correct 1409 ms 61420 KB Output is correct
41 Correct 645 ms 50240 KB Output is correct
42 Correct 576 ms 49252 KB Output is correct
43 Correct 205 ms 16256 KB Output is correct
44 Correct 1473 ms 73272 KB Output is correct
45 Correct 1477 ms 75184 KB Output is correct
46 Correct 1522 ms 82208 KB Output is correct
47 Correct 1691 ms 83384 KB Output is correct
48 Correct 1660 ms 80652 KB Output is correct
49 Correct 640 ms 47320 KB Output is correct
50 Correct 652 ms 47620 KB Output is correct
51 Correct 1846 ms 79368 KB Output is correct
52 Correct 915 ms 51176 KB Output is correct
53 Correct 19 ms 4344 KB Output is correct
54 Correct 1531 ms 75152 KB Output is correct
55 Correct 1377 ms 81664 KB Output is correct
56 Correct 1723 ms 83312 KB Output is correct
57 Correct 1089 ms 71480 KB Output is correct
58 Correct 1124 ms 72072 KB Output is correct
59 Correct 1250 ms 81768 KB Output is correct
60 Correct 1175 ms 71756 KB Output is correct
61 Correct 1190 ms 73556 KB Output is correct
62 Correct 705 ms 46956 KB Output is correct
63 Correct 50 ms 9336 KB Output is correct
64 Correct 978 ms 69212 KB Output is correct
65 Correct 894 ms 67220 KB Output is correct
66 Correct 679 ms 54648 KB Output is correct
67 Correct 750 ms 62584 KB Output is correct
68 Correct 565 ms 47224 KB Output is correct
69 Correct 1692 ms 83736 KB Output is correct
70 Correct 1273 ms 81120 KB Output is correct
71 Correct 1660 ms 80476 KB Output is correct
72 Correct 641 ms 47072 KB Output is correct
73 Correct 2262 ms 79344 KB Output is correct
74 Correct 780 ms 49308 KB Output is correct
75 Correct 800 ms 49316 KB Output is correct
76 Correct 1046 ms 54964 KB Output is correct
77 Correct 816 ms 56460 KB Output is correct
78 Correct 742 ms 51204 KB Output is correct
79 Correct 563 ms 47516 KB Output is correct
80 Correct 674 ms 47104 KB Output is correct
81 Correct 1480 ms 59888 KB Output is correct
82 Correct 642 ms 48628 KB Output is correct
83 Correct 568 ms 47864 KB Output is correct
84 Correct 155 ms 13048 KB Output is correct
85 Correct 1554 ms 78048 KB Output is correct
86 Correct 2491 ms 100924 KB Output is correct
87 Correct 103 ms 15096 KB Output is correct
88 Correct 134 ms 14872 KB Output is correct
89 Correct 112 ms 14968 KB Output is correct
90 Correct 41 ms 4984 KB Output is correct
91 Correct 9 ms 532 KB Output is correct
92 Correct 31 ms 3832 KB Output is correct
93 Correct 451 ms 35320 KB Output is correct
94 Correct 53 ms 9592 KB Output is correct
95 Correct 1073 ms 72668 KB Output is correct
96 Correct 893 ms 68028 KB Output is correct
97 Correct 786 ms 56220 KB Output is correct
98 Correct 798 ms 62416 KB Output is correct
99 Correct 3145 ms 121812 KB Output is correct
100 Correct 1522 ms 84656 KB Output is correct
101 Correct 2172 ms 93860 KB Output is correct
102 Correct 661 ms 48532 KB Output is correct
103 Correct 684 ms 50348 KB Output is correct
104 Correct 753 ms 50592 KB Output is correct
105 Correct 974 ms 55744 KB Output is correct
106 Correct 832 ms 51204 KB Output is correct
107 Correct 980 ms 55612 KB Output is correct
108 Correct 66 ms 6904 KB Output is correct
109 Correct 1178 ms 67900 KB Output is correct
110 Correct 1736 ms 83652 KB Output is correct
111 Correct 1349 ms 83400 KB Output is correct
112 Correct 825 ms 56956 KB Output is correct
113 Correct 703 ms 54976 KB Output is correct