제출 #1147888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147888		njoop	OBELISK (NOI14_obelisk)	C++17	0 / 25	467 ms	327680 KiB

obelisk

#include <bits/stdc++.h>
#define int long long
#define ti tuple<int, int, int>
using namespace std;

int k, m, h, cx, cy, cd, cf, ch, nd, nf, nh, sp[505][105];
vector<pair<int, int>> fl[505];
vector<ti> g[505][105];
priority_queue<ti, vector<ti>, greater<ti>> pq;

int findBDis(int dx, int dy) {
    int dis = 0;
    if(dx != 0) dis += dx+2;
    if(dy != 0) dis += dy+2;
    return dis;
}

int findDis(int x1, int y1, int x2, int y2) {
    int dis=0, dx = abs(x2-x1), dy = abs(y2-y1);
    dis += dx/(m+1)*2;
    dx %= m+1;
    dis += dy/(m+1)*2;
    dy %= m+1;
    return dis + min({findBDis(dx, dy), findBDis(abs(dx-m-1), dy)+2, findBDis(dx, abs(dy-m-1))+2, findBDis(abs(dx-m-1), abs(dy-m-1)+4)});
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> k >> m;
    cin >> cx >> cy;
    fl[0].push_back({cx, cy});
    cin >> cx >> cy;
    fl[k].push_back({cx, cy});
    for(int i=1; i<=k; i++) {
        cin >> h;
        h--;
        while(h--) {
            cin >> cx >> cy;
            fl[i].push_back({cx, cy});
        }
    }
    for(int i=1; i<=k; i++) {
        for(int a=0; a<fl[i].size(); a++) {
            for(int b=0; b<fl[i-1].size(); b++) {
                int x1 = fl[i][a].first, y1 = fl[i][a].second;
                int x2 = fl[i-1][b].first, y2 = fl[i-1][b].second;
                g[i-1][b].push_back({findDis(x1, y1, x2, y2), i, a});
            }
        }
    }
    pq.push({0, 0, 0});
    for(int i=0; i<505; i++) {
        for(int j=0; j<105; j++) {
            sp[i][j] = 1e18;
        }
    }
    sp[0][0] = 0;
    while(pq.size()) {
        cd = get<0>(pq.top());
        cf = get<1>(pq.top());
        ch = get<2>(pq.top());
        pq.pop();
        if(sp[cf][ch] < cd) continue;
        for(auto i: g[cf][ch]) {
            nd = get<0>(i);
            nf = get<1>(i);
            nh = get<2>(i);
            if(sp[nf][nh] > cd+nd) {
                sp[nf][nh] = cd+nd;
                pq.push({cd+nd, nf, nh});
            }
        }
    }
    cout << sp[k][0];
    return 0;
}

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