Submission #46926

#	Time	Username	Problem	Language	Result	Execution time	Memory
46926		golub	Soccer (JOI17_soccer)	C++14	100 / 100	1161 ms	47096 KiB

soccer

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,sse4")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("unroll-all-loops")

#include <bits/stdc++.h>

//#define TASK "lca"

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define pb push_back
#define int long long
#define pii pair<int, int>
#define len(x) (long long)x.size()

typedef long long ll;
typedef long double ld;

using namespace std;

const int INF = 1e18;
const int MAXN = 1e8;
const int MOD = 1e9 + 7;
const double EPS = 1e-12;

const vector<int> dx = {1, 0, -1, 0, 0, 1, 0, -1};

//char buf[(int)1e9];
//size_t p_ = 0;
//
//inline void *operator new(size_t n_) {
//    p_ += n_;
//    return buf + p_ - n_;
//}
//inline void operator delete(void*) {};

ll power(ll x, ll n, ll mod = 1e9 + 7) {
    if (n == 0) return 1ll;
    if (n & 1ll) return power(x, n - 1ll, mod) * x % mod;
    ll tmp = power(x, n >> 1ll, mod);
    return (tmp * tmp) % mod;
}

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd (b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

vector<vector<int>> g;
int h, w, A, B, C, n;

void precalc(queue<pii> q) {
    while (!q.empty()) {
        pii u = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            pii v = u;
            v.F += dx[i * 2]; v.S += dx[i * 2 + 1];
            if (v.F < 0 || v.F > h || v.S < 0 || v.S > w) continue;
            if (g[v.F][v.S] == INF) q.push(v);
            g[v.F][v.S] = min(g[v.F][v.S], g[u.F][u.S] + C);
        }
    }
}

struct node {
    int i, j, s;
    node(int i = 0, int j = 0, int s = 0) : i(i), j(j), s(s) {}
};

bool operator<(node a, node b) {
    return pair<pii, int>({{a.i, a.j}, a.s}) < pair<pii, int>({{b.i, b.j}, b.s});
}

signed main() {
#ifndef LOCAL
#ifdef TASK
    freopen(TASK".in", "r", stdin);
    freopen(TASK".out", "w", stdout);
#endif
#endif
#ifdef LOCAL
    //freopen("/Users/alekseygolub/Desktop/с++/ABS/ABS/input.txt", "r", stdin);
#endif
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(924653523);
    // == SOLUTION == //
    cin >> h >> w;
    g.resize(h + 1, vector<int>(w + 1, INF));
    cin >> A >> B >> C;
    cin >> n;
    queue<pii> q;
    vector<pii> players;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x][y] = 0;
        q.push({x, y});
        players.pb({x, y});
    }
    precalc(q);
    //map<node, bool> used;
    
    vector<vector<vector<int>>> dist(h + 1, vector<vector<int>>(w + 1, vector<int>(6, INF)));
    
    dist[players[0].F][players[0].S][0] = 0;
    
    set<pair<int, node>> calc;
    calc.insert({0, {players[0].F, players[0].S, 0}});
    
    while (!calc.empty()) {
        //while (!calc.empty() && used[(*calc.begin()).S]) calc.erase(calc.begin());
        //if (calc.empty()) break;
        node p = (*calc.begin()).S;
        int type = p.s;
        calc.erase(calc.begin());
        if (type == 0) {
            int cost = g[p.i][p.j];
            if (dist[p.i][p.j][1] > dist[p.i][p.j][0] + cost) {
                calc.erase({dist[p.i][p.j][1], {p.i, p.j, 1}});
                dist[p.i][p.j][1] = dist[p.i][p.j][0] + cost;
                calc.insert({dist[p.i][p.j][1], {p.i, p.j, 1}});
            }
        }
        if (type == 1) {
            
            if (dist[p.i][p.j][0] > dist[p.i][p.j][1]) {
                calc.erase({dist[p.i][p.j][0], {p.i, p.j, 0}});
                dist[p.i][p.j][0] = dist[p.i][p.j][1];
                calc.insert({dist[p.i][p.j][0], {p.i, p.j, 0}});
            }
            
            for (int i = 0; i < 4; i++) {
                int x = dx[i * 2], y = dx[i * 2 + 1];
                if (p.i + x < 0 || p.i + x > h || p.j + y < 0 || p.j + y > w) continue;
                int cost = C;
                if (dist[p.i + x][p.j + y][1] > dist[p.i][p.j][1] + cost) {
                    calc.erase({dist[p.i + x][p.j + y][1], {p.i + x, p.j + y, 1}});
                    dist[p.i + x][p.j + y][1] = dist[p.i][p.j][1] + cost;
                    calc.insert({dist[p.i + x][p.j + y][1], {p.i + x, p.j + y, 1}});
                }
            }
            
            for (int i = 2; i <= 5; i++) {
                int cost = B;
                if (dist[p.i][p.j][i] > dist[p.i][p.j][1] + cost) {
                    calc.erase({dist[p.i][p.j][i], {p.i, p.j, i}});
                    dist[p.i][p.j][i] = dist[p.i][p.j][1] + cost;
                    calc.insert({dist[p.i][p.j][i], {p.i, p.j, i}});
                }
            }
            
        }
        
        if (type >= 2) {
            assert(type <= 5);
            if (dist[p.i][p.j][0] > dist[p.i][p.j][type]) {
                calc.erase({dist[p.i][p.j][0], {p.i, p.j, 0}});
                dist[p.i][p.j][0] = dist[p.i][p.j][type];
                calc.insert({dist[p.i][p.j][0], {p.i, p.j, 0}});
            }
            
            int x = 0, y = 0;
            if (type == 2) {x = 1; y = 0;};
            if (type == 3) {x = -1, y = 0;};
            if (type == 4) {x = 0; y = -1;};
            if (type == 5) {x = 0; y = 1;};
            
            int cost = A;
            
            if (p.i + x < 0 || p.i + x > h || p.j + y < 0 || p.j + y > w) continue;
            
            if (dist[p.i + x][p.j + y][type] > dist[p.i][p.j][type] + cost) {
                calc.erase({dist[p.i + x][p.j + y][type], {p.i + x, p.j + y, type}});
                dist[p.i + x][p.j + y][type] = dist[p.i][p.j][type] + cost;
                calc.insert({dist[p.i + x][p.j + y][type], {p.i + x, p.j + y, type}});
            }
        }
        
    }
    cout << dist[players[n - 1].F][players[n - 1].S][0] << "\n";
}

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