Submission #67339966

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

using ll = long long;
using mint = modint998244353;

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    const int INF = 1 << 30;
    vector dp(H, vector<int>(W, INF));
    vector cand(H, vector<vector<int>>(W));
    using T = tuple<int, int, int>;
    priority_queue<T, vector<T>, greater<T>> que;
    vector<pair<int, int>> dir = {
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0}
    };
    auto inside = [&](int r, int c) {
        return (0 <= r && r < H && 0 <= c && c < W);
    };
    for(int i = 0; i < K; i++) {
        int r, c;
        cin >> r >> c;
        r--, c--;
        dp[r][c] = 0;
        que.push(T{0, r, c});
    }
    while(!que.empty()) {
        auto [d, r, c] = que.top();
        que.pop();
        if(dp[r][c] != d) continue;
        // cout << "# " << r + 1 << " " << c + 1 << " " << d << endl;
        for(const auto &[dr, dc] : dir) {
            int r2 = r + dr;
            int c2 = c + dc;
            if(inside(r2, c2)) {
                for(int i = 0; i <= cand[r2][c2].size(); i++) {
                    if(i == cand[r2][c2].size() || dp[r][c] < cand[r2][c2][i]) {
                        cand[r2][c2].insert(cand[r2][c2].begin() + i, dp[r][c] + 1);
                        break;
                    }
                }
                // cout << dp[r][c] << endl;
                if(cand[r2][c2].size() >= 2 && dp[r2][c2] > cand[r2][c2][1]) {
                    dp[r2][c2] = cand[r2][c2][1];
                    que.push(T{dp[r2][c2], r2, c2});
                    // cout << "# " << r2 + 1 << " " << c2 + 1 << " " << dp[r2][c2] << endl;
                    // for(int x : cand[r2][c2]) cout << x << " "; cout << endl;
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            if(dp[i][j] < INF) ans += dp[i][j];
            // if(dp[i][j] < INF) cout << dp[i][j] << " ";
            // else cout << ". ";
        }
        // cout << endl;
    }
    cout << ans << endl;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:43:34: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   43 |                 for(int i = 0; i <= cand[r2][c2].size(); i++) {
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:44:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   44 |                     if(i == cand[r2][c2].size() || dp[r][c] < cand[r2][c2][i]) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~

Judge Result