結果
問題 | No.2695 Warp Zone |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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 DEBUGvoid 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...);}#elsetemplate<typename... Args>void dbg(const Args &... args) {}#endiftemplate<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;}