Submission #333737

#	Time	Username	Problem	Language	Result	Execution time	Memory
333737		ncduy0303	OBELISK (NOI14_obelisk)	C++17	25 / 25	433 ms	214252 KiB

obelisk

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_M = 1e5 + 1;
const int MAX_K = 5e2 + 1;
const int MAX_H = 1e2 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

const int dx[] = {-1, 1, 0};

int m, k, psz[MAX_K];
ar<int,2> s, e;
vector<ar<int,2>> holes[MAX_K], adj[MAX_K * MAX_H];
vector<int> dist;

int calc(int x, int y) {
    if (m == 1) return abs(x) + abs(y);
    int res = INF;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int g = 0; g < 2; g++) {
                for (int h = 0; h < 2; h++) {
                    int p = abs(x + dx[i] * (m + 1)),
                        q = abs(y + dx[j] * (m + 1)),
                        t1 = p / (m + 1) + (i < 2),
                        t2 = q / (m + 1) + (j < 2),
                        cur = t1 * 2 + t2 * 2 + g * 2 + h * 2;
 
                    p %= (m + 1);
                    q %= (m + 1);
 
                    if (p) {
                        if (!t2)
                            cur += 2;
                        if (g)
                            cur += m + 1 - p;
                        else
                            cur += p;
                    }
 
                    if (q) {
                        if (!t1)
                            cur += 2;
                        if (h)
                            cur += m + 1 - q;
                        else
                            cur += q;
                    }
 
                    res = min(res, cur);
                }
            }
        }
    }
    return res;
}

void dijk(int s) {
    dist.assign(MAX_K * MAX_M, INF);
    priority_queue<ar<int,2>, vector<ar<int,2>>, greater<ar<int,2>>> pq;
    dist[s] = 0; pq.push({0, s});
    while (pq.size()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    } 
}

void solve() {
    cin >> k >> m >> s[0] >> s[1] >> e[0] >> e[1];
    holes[k].push_back(s);
    holes[0].push_back(e);
    for (int i = k - 1; i > 0; i--) {
        int h; cin >> h;
        while (h--) {
            int x, y; cin >> x >> y;
            holes[i].push_back({x, y});
        }
    }
    for (int i = 0; i < k; i++) {
        psz[i + 1] = psz[i] + holes[i].size();
    }
    for (int i = 1; i <= k; i++) {
        for (int u = 0; u < holes[i].size(); u++) {
            for (int v = 0; v < holes[i - 1].size(); v++) {
                int dist = calc(holes[i - 1][v][0] - holes[i][u][0], holes[i - 1][v][1] - holes[i][u][1]);
                adj[u + psz[i]].push_back({v + psz[i - 1], dist});
            }
        }
    }
    dijk(psz[k]);
    cout << dist[0] << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

Compilation message (stderr)

obelisk.cpp: In function 'void solve()':
obelisk.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int u = 0; u < holes[i].size(); u++) {
      |                         ~~^~~~~~~~~~~~~~~~~
obelisk.cpp:96:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             for (int v = 0; v < holes[i - 1].size(); v++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~

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