Submission #1180318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180318		anteknne	Soccer (JOI17_soccer)	C++20	100 / 100	328 ms	22916 KiB

soccer

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 100 * 1000 + 17;
const int MAXW = 500 + 17;
const int K = 5;
//4 - ma pile
//0, 1, 2, 3 - kierunki bez
pii gracze[MAXN];
ll odl[MAXW][MAXW];
bool odw[MAXW][MAXW];
ll wyn[MAXW][MAXW][K];
bool odw2[MAXW][MAXW][K];
deque<pair<pii, ll>> d;
vector<pii> przesuniecia = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int w, h;

struct el {
    int x;
    int y;
    int typ;
    ll zodl;
};

struct porownaj {
    bool operator () (el a, el b) {
        return a.zodl > b.zodl;
    }
};

priority_queue<el, vector<el>, porownaj> pq;

vector<pair<int, pii>> gensasiedzi (pii a) {
    vector<pair<int, pii>> wyn;
    wyn.clear();
    int cnt = 0;
    for (auto x : przesuniecia) {
        if (a.st + x.st <= w && a.st + x.st >= 0 && a.nd + x.nd <= h && a.nd + x.nd >= 0) {
            wyn.pb({cnt, {a.st + x.st, a.nd + x.nd}});
        }
        cnt ++;
    }
    return wyn;
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    ll a, b, c;
    cin >> w >> h >> a >> b >> c >> n;

    for (int i = 0; i < n; i ++) {
        cin >> gracze[i].st >> gracze[i].nd;
    }

    for (int i = 0; i <= w; i ++) {
        for (int j = 0; j <= h; j ++) {
            odl[i][j] = LLONG_MAX;
        }
    }

    for (int i = 0; i < n - 1; i ++) {
        d.pb({gracze[i], 0});
        odl[gracze[i].st][gracze[i].nd] = 0;
    }

    while (!d.empty()) {
        pii v = d.front().st;
        ll aktodl = d.front().nd;
        d.pop_front();

        if (odw[v.st][v.nd]) {
            continue;
        }

        odw[v.st][v.nd] = true;
        for (auto x2 : gensasiedzi(v)) {
            pii x = x2.nd;
            if (odl[x.st][x.nd] > aktodl + 1) {
                odl[x.st][x.nd] = aktodl + 1;
                d.pb({x, odl[x.st][x.nd]});
            }
        }
    }

    if (debug) {
        cout << "odlegosci: " << "\n";
        for (int i = 0; i <= w; i ++) {
            for (int j = 0; j <= h; j ++) {
                cout << i << " " << j << ": " << odl[i][j] << "\n";
            }
        }
    }

    odl[gracze[n - 1].st][gracze[n - 1].nd] = 0;
    for (int i = 0; i <= w; i ++) {
        for (int j = 0; j <= h; j ++) {
            for (int k = 0; k < K; k ++) {
                wyn[i][j][k] = LLONG_MAX;
            }
        }
    }
    el startowy;
    startowy.x = gracze[0].st;
    startowy.y = gracze[0].nd;
    startowy.zodl = 0;
    startowy.typ = 4;
    pq.push(startowy);
    wyn[gracze[0].st][gracze[0].nd][4] = 0;

    while (!pq.empty()) {
        el v = pq.top();
        pq.pop();
        if (odw2[v.x][v.y][v.typ]) {
            continue;
        }
        odw2[v.x][v.y][v.typ] = true;

        if (v.typ != 4) {
            ll noweodl = odl[v.x][v.y] * c + v.zodl;
            if (noweodl < wyn[v.x][v.y][4]) {
                wyn[v.x][v.y][4] = noweodl;
                pq.push({v.x, v.y, 4, noweodl});
            }

            noweodl = v.zodl + a;
            ll nx = v.x + przesuniecia[v.typ].st;
            ll ny = v.y + przesuniecia[v.typ].nd;

            if (nx <= w && nx >= 0 && ny <= h && ny >= 0) {
                if (noweodl < wyn[nx][ny][v.typ]) {
                    wyn[nx][ny][v.typ] = noweodl;
                    pq.push({nx, ny, v.typ, noweodl});
                }
            }


        } else {
            for (auto x2 : gensasiedzi({v.x, v.y})) {
                pii x = x2.nd;
                ll noweodl = v.zodl + a + b;
                if (noweodl < wyn[x.st][x.nd][x2.st]) {
                    wyn[x.st][x.nd][x2.st] = noweodl;
                    pq.push({x.st, x.nd, x2.st, noweodl});
                }
                noweodl = v.zodl + c;
                if (noweodl < wyn[x.st][x.nd][4]) {
                    wyn[x.st][x.nd][4] = noweodl;
                    pq.push({x.st, x.nd, 4, noweodl});
                }
            }
        }
    }

    cout << wyn[gracze[n - 1].st][gracze[n - 1].nd][4] << "\n";


    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:148:30: warning: narrowing conversion of 'nx' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  148 |                     pq.push({nx, ny, v.typ, noweodl});
      |                              ^~
soccer.cpp:148:34: warning: narrowing conversion of 'ny' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  148 |                     pq.push({nx, ny, v.typ, noweodl});
      |                                  ^~

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