제출 #1103068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103068		jnjwnwnw	오벨리스크 (NOI14_obelisk)	C++17	5 / 25	225 ms	5308 KiB

obelisk

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>

using namespace std;

#define ll long long
#define fff(i, a, b) for(int i = a; i < b; i++)
#define fffm(i, a, b) for(int i = a; i > b; i--)
#define ff(a, c) for(auto a: c)
#define x first
#define y second

#define MAXK 505
ll k, m;
pair<ll, ll> strt, nd;
vector<pair<ll, ll>> floors[MAXK];
ll dist(pair<ll, ll> p1, pair<ll, ll> p2){
    if (m == 1) return abs(p1.x-p2.x) + abs(p1.y-p2.y);
    return (abs(p1.x-p2.x) % (m+1)) + (abs(p1.y-p2.y) % (m+1)) + 2*(max(abs(p1.x-p2.x)/(m+1), (p1.x-p2.x) ? 1ll:0ll)) + 2*(max(abs(p1.y-p2.y)/(m+1), (p1.y-p2.y) ? 1ll:0ll));
}

priority_queue<pair<pair<ll, int>, pair<ll, ll>>> q;
set<pair<ll, ll>> seen[MAXK];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> k >> m;
    cin >> strt.x >> strt.y >> nd.x >> nd.y;
    fffm(i, k-1, 0){
        ll ln; cin >> ln;
        fff(j, 0, ln){
            pair<ll, ll> a;
            cin >> a.x >> a.y;
            floors[i].push_back(a);
        }
    }
    q.push({{0, k}, strt});
    ll ans = INT64_MAX;
    while(q.size()){
        auto [a, pt] = q.top(); q.pop();
        auto [dst, flr] = a;
        if (seen[flr].find(pt) != seen[flr].end()){
            continue;
        }
        seen[flr].insert(pt);
        if (flr == 1){
            ans = min(ans, -dst + dist(pt, nd));
        }else{
            ff(p2, floors[flr-1]){
                ll d2 = dst - dist(pt, p2);
                q.push({{d2, flr-1}, p2});
            }
        }
    }
    cout << ans << endl;
}   

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7