Submission #1180251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180251		patgra	Soccer (JOI17_soccer)	C++20	100 / 100	274 ms	17984 KiB

soccer

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

ll h, w, n;
ll a, b, c;
vector<vector<ll>> distFromPlayer;
vector<ll> distFromStart;
vector<pair<int, int>> players;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> h >> w >> a >> b >> c >> n;
    h++; w++;
    distFromPlayer.resize(h, vector<ll>(w, -1));
    players.resize(n);
    distFromStart.resize(5 * h * w, 1e18);
    rep(i, 0, n) { ll x, y; cin >> x >> y, players[i] = {x, y}; }
    queue<pair<int, int>> q;
    repIn(i, players) q.push(i);
    repIn2(i, j, players) distFromPlayer[i][j] = 0;
    while(!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        auto md = distFromPlayer[x][y];
        array<pair<int, int>, 4> xddd = {{{-1, 0}, {1, 0}, {0, 1}, {0, -1}}};
        repIn2(dx, dy, xddd) {
            if(x + dx < 0 || x + dx >= h || y + dy < 0 || y + dy >= w) continue;
            if(distFromPlayer[x + dx][y + dy] != -1) continue;
            distFromPlayer[x + dx][y + dy] = md + 1;
            q.push({x + dx, y + dy});
        }
    }
    DEBUG {
        DC << "Dist from player: " << eol;
        rep(i, 0, h) { rep(j, 0, w) DC << distFromPlayer[i][j] << ' '; DC << eol; }
    }
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> Q;
    auto [xx, yy] = players[0];
    distFromStart[xx * w + yy] = 0;
    Q.push({0, xx * w + yy});
    while(!Q.empty()) {
        auto [md, v] = Q.top();
        Q.pop();
        if(md > distFromStart[v]) continue;
        auto x = v / w;
        auto y = v % w;
        auto tp = x / h;
        x %= h;
        DEBUG {
            bool g = false;
            repIn2(i, j, players) if(i == x && j == y) g = true;
            if(g) {
                DC << x << ' ' << y << ' ' << tp << ' ' << md;
                DC << eol;
                DC << "";
            }
        }
        if((tp == 0 || tp == 1) && x < h - 1) {
            auto v2 = v + w;
            auto md2 = md + (tp == 0 ? c : a);
            if(distFromStart[v2] > md2) distFromStart[v2] = md2, Q.push({md2, v2});
        }
        if((tp == 0 || tp == 2) && x > 0) {
            auto v2 = v - w;
            auto md2 = md + (tp == 0 ? c : a);
            if(distFromStart[v2] > md2) distFromStart[v2] = md2, Q.push({md2, v2});
        }
        if((tp == 0 || tp == 3) && y < w - 1) {
            auto v2 = v + 1;
            auto md2 = md + (tp == 0 ? c : a);
            if(distFromStart[v2] > md2) distFromStart[v2] = md2, Q.push({md2, v2});
        }
        if((tp == 0 || tp == 4) && y > 0) {
            auto v2 = v - 1;
            auto md2 = md + (tp == 0 ? c : a);
            if(distFromStart[v2] > md2) distFromStart[v2] = md2, Q.push({md2, v2});
        }
        if(tp == 0) {
            rep(i, 1, 5) {
                auto v2 = v + h * w * i;
                auto md2 = md + b;
                if(distFromStart[v2] > md2) distFromStart[v2] = md2, Q.push({md2, v2});
            }
        }
        else {
            auto v2 = x * w + y;
            auto md2 = md + distFromPlayer[x][y] * c;
            if(distFromStart[v2] > md2) distFromStart[v2] = md2, Q.push({md2, v2});
        }
    }
    auto [X, Y] = players[n - 1];
    cout << distFromStart[X * w + Y] << '\n';
   
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65