oj.uz

Submission #1048849

# Submission time Handle Problem Language Result Execution time Memory
1048849 2024-08-08T09:52:43 Z MercubytheFirst Sky Walking (IOI19_walk) C++17
10 / 100
 404 ms 1048576 KB 
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
using ll = long long;
const ll inf = 1e15 + 37;

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);

template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g) {
	ll n = x.size(), m = l.size();
	l.push_back(-1);
	r.push_back(1e9 + 37);
	y.push_back(0);
	auto intr = [&](ll i, ll j) -> bool
	{
		return l[j] <= i and i <= r[j] and h[i] >= y[j];
	};

	vector<vector<ll> > dist(n, vector<ll>(m + 1, inf));
	min_heap<array<ll, 3> > pq;
	for(ll i = 0; i < m; ++i) {
		if(intr(s, i)) {
			pq.push({y[i], s, i});
			// cout << i << " : " << y[i] << endl;
		}
	}
	while(!pq.empty()) {
		auto [d, i, j] = pq.top();
		pq.pop();
		if(dist[i][j] != inf) {
			continue;
		}
		dist[i][j] = d;
		for(ll ii = 0; ii < n; ++ii) {
			for(ll jj = 0; jj < m; ++jj) {
				if(!intr(ii, jj) or !intr(i, jj) or dist[ii][jj] != inf) {
					continue;
				}
				pq.push({dist[i][j] + abs(y[j] - y[jj]) + abs(x[i] - x[ii]), ii, jj});
			}
		}
	}
	ll ans = inf;
	for(int i = 0; i < m; ++i) {
		if(!intr(g, i)) {
			continue;
		}
		ans = min(ans, dist[g][i] + y[i]);
	}
	if(ans == inf)
		ans = -1;
	return ans;
}


template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
  os << "[";
  for(size_t i = 0; i + 1 < N; ++i) {
    os << a[i] << ", ";
  }
  if(N > 0)
    os << a[N - 1];
  os << "]";
  return os;
}
 
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ") ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << '[';
  for(auto x : v)
    os << x << ", ";
  os << "] ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}
//
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}


/*
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 16 ms 2008 KB Output is correct
6 Correct 12 ms 2072 KB Output is correct
7 Correct 11 ms 2004 KB Output is correct
8 Correct 8 ms 1372 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 35 ms 3616 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 30 ms 3540 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 404 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 342 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 342 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 16 ms 2008 KB Output is correct
6 Correct 12 ms 2072 KB Output is correct
7 Correct 11 ms 2004 KB Output is correct
8 Correct 8 ms 1372 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 35 ms 3616 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 30 ms 3540 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Runtime error 404 ms 1048576 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -