oj.uz

Submission #155081

# Submission time Handle Problem Language Result Execution time Memory
155081 2019-09-26T07:54:45 Z wakaka Sky Walking (IOI19_walk) C++14
33 / 100
 2064 ms 82204 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);
		}
	}
	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:66:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vert[i].size(); ++j) {
                   ~~~~~~^~~~~~~~~~~~~~~~
walk.cpp:77:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < hor[i].size(); ++j) {
                   ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 15864 KB Output is correct
2 Correct 1476 ms 71784 KB Output is correct
3 Correct 1434 ms 74248 KB Output is correct
4 Correct 1518 ms 80928 KB Output is correct
5 Correct 1761 ms 81756 KB Output is correct
6 Correct 1605 ms 77460 KB Output is correct
7 Correct 651 ms 45304 KB Output is correct
8 Correct 644 ms 45816 KB Output is correct
9 Correct 2064 ms 74604 KB Output is correct
10 Correct 1070 ms 48112 KB Output is correct
11 Correct 20 ms 3576 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 15864 KB Output is correct
2 Correct 1476 ms 71784 KB Output is correct
3 Correct 1434 ms 74248 KB Output is correct
4 Correct 1518 ms 80928 KB Output is correct
5 Correct 1761 ms 81756 KB Output is correct
6 Correct 1605 ms 77460 KB Output is correct
7 Correct 651 ms 45304 KB Output is correct
8 Correct 644 ms 45816 KB Output is correct
9 Correct 2064 ms 74604 KB Output is correct
10 Correct 1070 ms 48112 KB Output is correct
11 Correct 20 ms 3576 KB Output is correct
12 Correct 1701 ms 74024 KB Output is correct
13 Correct 1546 ms 80088 KB Output is correct
14 Correct 1877 ms 81788 KB Output is correct
15 Correct 1115 ms 69972 KB Output is correct
16 Correct 1116 ms 70480 KB Output is correct
17 Correct 1219 ms 80124 KB Output is correct
18 Correct 1113 ms 69976 KB Output is correct
19 Correct 1186 ms 70460 KB Output is correct
20 Correct 764 ms 44024 KB Output is correct
21 Correct 48 ms 7288 KB Output is correct
22 Correct 1000 ms 65912 KB Output is correct
23 Correct 848 ms 64120 KB Output is correct
24 Correct 652 ms 51360 KB Output is correct
25 Correct 848 ms 59256 KB Output is correct
26 Correct 585 ms 44152 KB Output is correct
27 Correct 1747 ms 82204 KB Output is correct
28 Correct 1245 ms 79564 KB Output is correct
29 Correct 1737 ms 77488 KB Output is correct
30 Correct 645 ms 45300 KB Output is correct
31 Correct 1667 ms 74376 KB Output is correct
32 Correct 684 ms 47388 KB Output is correct
33 Correct 719 ms 47436 KB Output is correct
34 Correct 1118 ms 54896 KB Output is correct
35 Correct 847 ms 57796 KB Output is correct
36 Correct 646 ms 52788 KB Output is correct
37 Correct 600 ms 49148 KB Output is correct
38 Correct 735 ms 48820 KB Output is correct
39 Correct 1070 ms 58904 KB Output is correct
40 Correct 606 ms 50396 KB Output is correct
41 Correct 588 ms 49696 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -