結果

問題 No.2695 Warp Zone
ユーザー 黒狗さん。黒狗さん。
提出日時 2024-03-22 22:35:59
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,951 bytes
コンパイル時間 2,184 ms
コンパイル使用メモリ 193,516 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-03-22 22:36:02
合計ジャッジ時間 3,128 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,548 KB
testcase_01 WA -
testcase_02 AC 2 ms
6,548 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 2 ms
6,548 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 2 ms
6,548 KB
testcase_26 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:18:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   18 |     is >> p.first >> p.second;
      |              ^
main.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   21 | 
      |              ^
main.cpp:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   22 | template <typename T>
      |              ^

ソースコード

diff # 

#line 2 "kyopro_lib/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << p.first << " " << p.second;
    return os;
}
ll sum(vector<ll> a){
    ll res = 0;
    for(auto x:a) res += x;
    return res;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    ll s = (ll)v.size();
    for (ll i = 0; i < s; i++) os << (i ? " " : "") << v[i];
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (auto &x : v) is >> x;
    return is;
}
#define rep(i, n) for (ll (i) = 0; (i) < (ll)(n); (i)++)
#line 2 "main.cpp"
signed main(){
    ll H,W,N;
    cin >> H >> W >> N;
    H--;W--;
    map<pair<ll,ll>,ll> mp;
    priority_queue<pair<ll,pair<pair<ll,ll>,pair<ll,ll>>>, vector<pair<ll,pair<pair<ll,ll>,pair<ll,ll>>>>, greater<pair<ll,pair<pair<ll,ll>,pair<ll,ll>>>>> q;
    rep(i,N)
    {
        ll a,b,c,d;
        cin >> a >> b >> c >> d;
        a--;b--;c--;d--;
        q.push({min(a+b,c+d),{{a,b},{c,d}}});
    }
    ll finaly = H+W;
    while(!q.empty())
    {
        auto [_,p] = q.top();
        q.pop();
        if (mp[p.first] == 0 and mp[p.second] == 0) continue;
        auto [a,b] = p.first;
        auto [c,d] = p.second;
        if (mp[{a,b}] == 0)
        {
            mp[{a,b}] = a+b;
            for(auto x:mp)
            {
                if (x.second != 0)
                {
                    mp[{a,b}] = min(mp[{x.first.first,x.first.second}]+abs(a+b-x.first.first-x.first.second),mp[{a,b}]);
                }
            }
        }else
        {
            mp[{a,b}] = min(a+b,mp[{a,b}]);
            for(auto x:mp)
            {
                if (x.second != 0)
                {
                    mp[{a,b}] = min(mp[{x.first.first,x.first.second}]+abs(a+b-x.first.first-x.first.second),mp[{a,b}]);
                }
            }
        }
        if (mp[{c,d}] == 0)
        {
            mp[{c,d}] = min(c+d,mp[{a,b}]+1);
            for(auto x:mp)
            {
                if (x.second != 0)
                {
                    mp[{c,d}] = min(mp[{x.first.first,x.first.second}]+abs(c+d-x.first.first-x.first.second),mp[{c,d}]);
                }
            }
        }else
        {
            mp[{c,d}] = min(c+d,min(mp[{c,d}],mp[{a,b}]+1));
            for(auto x:mp)
            {
                if (x.second != 0)
                {
                    mp[{c,d}] = min(mp[{x.first.first,x.first.second}]+abs(c+d-x.first.first-x.first.second),mp[{c,d}]);
                }
            }
        }
        finaly = min(finaly,H+W-c-d+mp[{c,d}]);
        finaly = min(finaly,H+W-a-b+mp[{a,b}]);
    }
    cout << finaly << endl;
}
0