oj.uz

Submission #155080

# Submission time Handle Problem Language Result Execution time Memory
155080 2019-09-26T07:45:35 Z wakaka Sky Walking (IOI19_walk) C++14
15 / 100
 1921 ms 86104 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) {
		return y[a] < y[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:65:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vert[i].size(); ++j) {
                   ~~~~~~^~~~~~~~~~~~~~~~
walk.cpp:76: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 376 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 172 ms 15120 KB Output is correct
2 Correct 1504 ms 73636 KB Output is correct
3 Correct 1557 ms 76364 KB Output is correct
4 Correct 1563 ms 84852 KB Output is correct
5 Correct 1721 ms 85884 KB Output is correct
6 Correct 1585 ms 81664 KB Output is correct
7 Correct 743 ms 48360 KB Output is correct
8 Correct 758 ms 49844 KB Output is correct
9 Correct 1921 ms 78732 KB Output is correct
10 Correct 833 ms 51464 KB Output is correct
11 Correct 19 ms 4216 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 15120 KB Output is correct
2 Correct 1504 ms 73636 KB Output is correct
3 Correct 1557 ms 76364 KB Output is correct
4 Correct 1563 ms 84852 KB Output is correct
5 Correct 1721 ms 85884 KB Output is correct
6 Correct 1585 ms 81664 KB Output is correct
7 Correct 743 ms 48360 KB Output is correct
8 Correct 758 ms 49844 KB Output is correct
9 Correct 1921 ms 78732 KB Output is correct
10 Correct 833 ms 51464 KB Output is correct
11 Correct 19 ms 4216 KB Output is correct
12 Correct 1617 ms 76192 KB Output is correct
13 Correct 1503 ms 84068 KB Output is correct
14 Correct 1919 ms 85992 KB Output is correct
15 Correct 1123 ms 73680 KB Output is correct
16 Correct 1206 ms 74444 KB Output is correct
17 Correct 1274 ms 84272 KB Output is correct
18 Correct 1095 ms 73696 KB Output is correct
19 Correct 1145 ms 74532 KB Output is correct
20 Correct 731 ms 47032 KB Output is correct
21 Correct 49 ms 9200 KB Output is correct
22 Correct 978 ms 69528 KB Output is correct
23 Correct 865 ms 67884 KB Output is correct
24 Correct 662 ms 55048 KB Output is correct
25 Correct 762 ms 63048 KB Output is correct
26 Correct 681 ms 47880 KB Output is correct
27 Correct 1678 ms 86104 KB Output is correct
28 Correct 1307 ms 83608 KB Output is correct
29 Correct 1748 ms 81528 KB Output is correct
30 Correct 662 ms 48356 KB Output is correct
31 Correct 1886 ms 78336 KB Output is correct
32 Correct 709 ms 50424 KB Output is correct
33 Incorrect 699 ms 50648 KB Output isn't correct
34 Halted 0 ms 0 KB -

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 -