結果

問題 No.2695 Warp Zone
ユーザー KowerKoint2010KowerKoint2010
提出日時 2024-03-12 23:27:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 6,601 bytes
コンパイル時間 2,979 ms
コンパイル使用メモリ 262,392 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-29 22:28:31
合計ジャッジ時間 3,656 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#line 2 "/home/kowerkoint/workspace/CompPro-Make/library/KowerKoint/stl-expansion.hpp"
#include <bits/stdc++.h>
template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) {
is >> p.first >> p.second;
return is;
}
template <typename T, size_t N>
std::istream& operator>>(std::istream& is, std::array<T, N>& a) {
for (size_t i = 0; i < N; ++i) {
is >> a[i];
}
return is;
}
template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for (auto& e : v) is >> e;
return is;
}
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, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
for (size_t i = 0; i < N; ++i) {
os << a[i] << (i + 1 == a.size() ? "" : " ");
}
return os;
}
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
for (size_t i = 0; i < v.size(); ++i) {
os << v[i] << (i + 1 == v.size() ? "" : " ");
}
return os;
}
#line 3 "/home/kowerkoint/workspace/CompPro-Make/library/KowerKoint/base.hpp"
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define END(...) { print(__VA_ARGS__); return; }
template <typename T>
inline auto rep(T n) { return views::iota(T(0), n); }
template <typename T>
inline auto rep(T st, T ed, T step = 1) { return views::iota(T(0), (ed - st) / step) | views::transform([st, step](T i) { return st + i * step; }); }
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
using ll = long long;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
using ull = unsigned long long;
using VUL = vector<ull>;
using VVUL = vector<VUL>;
using VVVUL = vector<VVUL>;
using VD = vector<double>;
using VVD = vector<VD>;
using VVVD = vector<VVD>;
using VS = vector<string>;
using VVS = vector<VS>;
using VVVS = vector<VVS>;
using VC = vector<char>;
using VVC = vector<VC>;
using VVVC = vector<VVC>;
using P = pair<int, int>;
using VP = vector<P>;
using VVP = vector<VP>;
using VVVP = vector<VVP>;
using LP = pair<ll, ll>;
using VLP = vector<LP>;
using VVLP = vector<VLP>;
using VVVLP = vector<VVLP>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;
constexpr int INF = 1001001001;
constexpr ll LINF = 1001001001001001001ll;
constexpr int DX[] = {1, 0, -1, 0};
constexpr int DY[] = {0, 1, 0, -1};
void print() { cout << '\n'; }
template<typename T>
void print(const T &t) { cout << t << '\n'; }
template<typename Head, typename... Tail>
void print(const Head &head, const Tail &... tail) {
cout << head << ' ';
print(tail...);
}
#ifdef DEBUG
void dbg() { cerr << '\n'; }
template<typename T>
void dbg(const T &t) { cerr << t << '\n'; }
template<typename Head, typename... Tail>
void dbg(const Head &head, const Tail &... tail) {
cerr << head << ' ';
dbg(tail...);
}
#else
template<typename... Args>
void dbg(const Args &... args) {}
#endif
template<typename T>
vector<vector<T>> split(typename vector<T>::const_iterator begin, typename vector<T>::const_iterator end, T val) {
vector<vector<T>> res;
vector<T> cur;
for(auto it = begin; it != end; it++) {
if(*it == val) {
res.push_back(cur);
cur.clear();
} else cur.push_back(*it);
}
res.push_back(cur);
return res;
}
vector<string> split(typename string::const_iterator begin, typename string::const_iterator end, char val) {
vector<string> res;
string cur = "";
for(auto it = begin; it != end; it++) {
if(*it == val) {
res.push_back(cur);
cur.clear();
} else cur.push_back(*it);
}
res.push_back(cur);
return res;
}
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template <typename T>
pair<VI, vector<T>> compress(const vector<T> &a) {
int n = a.size();
vector<T> x;
REP(i, n) x.push_back(a[i]);
sort(ALL(x)); x.erase(unique(ALL(x)), x.end());
VI res(n);
REP(i, n) res[i] = lower_bound(ALL(x), a[i]) - x.begin();
return make_pair(res, x);
}
template <typename It>
auto rle(It begin, It end) {
vector<pair<typename It::value_type, int>> res;
if(begin == end) return res;
auto pre = *begin;
int num = 1;
for(auto it = begin + 1; it != end; it++) {
if(pre != *it) {
res.emplace_back(pre, num);
pre = *it;
num = 1;
} else num++;
}
res.emplace_back(pre, num);
return res;
}
template <typename It>
vector<pair<typename It::value_type, int>> rle_sort(It begin, It end) {
vector<typename It::value_type> cloned(begin, end);
sort(ALL(cloned));
auto e = rle(ALL(cloned));
sort(ALL(e), [](const auto& l, const auto& r) { return l.second < r.second; });
return e;
}
template <typename T>
pair<vector<T>, vector<T>> factorial(int n) {
vector<T> res(n+1), rev(n+1);
res[0] = 1;
REP(i, n) res[i+1] = res[i] * (i+1);
rev[n] = 1 / res[n];
for(int i = n; i > 0; i--) {
rev[i-1] = rev[i] * i;
}
return make_pair(res, rev);
}
#line 2 "main.cpp"
void solve(){
ll h, w, n; cin >> h >> w >> n;
VLP points(n*2); cin >> points;
VL dist(n*2);
auto md = [](LP x, LP y) { return abs(x.first-y.first) + abs(x.second-y.second); };
GPQ<pair<ll, int>> pq;
for(int i : rep(n*2)) {
pq.emplace(dist[i] = md(points[i], {1, 1}), i);
}
while(!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if(d > dist[u]) continue;
for(int v : rep(n*2)) {
if(chmin(dist[v], d + md(points[u], points[v]))) pq.emplace(dist[v], v);
}
if(u % 2 == 0) {
int v = u+1;
if(chmin(dist[v], d + 1)) pq.emplace(dist[v], v);
}
}
ll ans = md({1, 1}, {h, w});
for(int i : rep(n*2)) chmin(ans, dist[i] + md(points[i], {h, w}));
print(ans);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(10);
int t = 1;
// cin >> t;
for(int case_id = 1; case_id <= t; case_id++) solve();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0