Submission #685424

#	Time	Username	Problem	Language	Result	Execution time	Memory
685424		coffee5427	Soccer (JOI17_soccer)	C++17	5 / 100	1517 ms	262144 KiB

soccer

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;
using PQ = priority_queue<int, vector<int>, greater<int>>;
 
const int INF = 2e18;
const int maxn = 500 + 5;
const int W = 505;
const int maxm = 1e6 + 5;
const int M = 1e9 + 7;

int n, m, t;
int A, B, C;
int dis[maxn * maxn * 6 + 5];
int head[W * W * 6], dt[W][W];
int sum, cnt;
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
queue<pii> q;
vector<pii> pt;

struct E {
    int v, w, next = -1;
} edge[W * W * 36];

void build () {
    while (q.size ()) {
        auto [i, j] = q.front ();
        q.pop ();

        for (auto [u, v] : d) {
            int ni = i + u, nj = j + v;
            if (ni > n || ni < 0 || nj > m || nj < 0) continue;
            if (dt[ni][nj] < INF) continue;
            
            dt[ni][nj] = dt[i][j] + 1;
            q.push ({ni, nj});
        }
    }
}

string de (int p) {
    int j = p % (m + 1);
    int i = (p - j) / (m + 1);
   
    cout << "(" << i << "," << j << ")";
    return "";
}

string print (int u) {
    int k = u / sum;
    int p = u - k * sum;

    cout << "p:" << de (p) << ",k:" << k;
    return "";
}

void add_edge (int u, int v, int w) {
    edge[cnt].v = v, edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
    cnt++;
}

int id (int i, int j) {
    return i * (m + 1) + j;
}

void dijkstra () {
    memset (dis, 0x3f, sizeof dis);
    priority_queue <pii, vector<pii>, greater<>> pq;
    
    int pos = id (pt[1].F, pt[1].S);
    pq.push ({0, pos + 4 * sum});

    while (pq.size ()) {
        auto [W, u] = pq.top ();
        pq.pop ();
        
        if (dis[u] < INF) continue;
        dis[u] = W;

        for (int i = head[u];; i = edge[i].next) {
            //cout << "i:" << i << "\n";
            if (i == -1) break;
            int v = edge[i].v, w = edge[i].w;
            pq.push ({W + w, v});
        }
    }
}

void init () {
    memset (dt, 0x3f, sizeof dt);
    memset (head, -1, sizeof head);
    cin >> n >> m;
    cin >> A >> B >> C;
    cin >> t;
    sum = (n + 1) * (m + 1);
    pt.resize (t + 1);

    for (int i = 1; i <= t; i++) {
        int &x = pt[i].F, &y = pt[i].S;
        cin >> x >> y;
        q.push ({x, y});
        dt[x][y] = 0;
    }
}

void solve () {
    build ();

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            int p = id (i, j);
            for (int k = 0; k < 4; k++) {
                add_edge (p + k * sum, p + 4  * sum, 0);
                add_edge (p + 5 * sum, p + k * sum, B);
                add_edge (p + 4 * sum, p + 5 * sum, dt[i][j] * C);

                int ni = i + d[k][0], nj = j + d[k][1];
                if (ni > n || ni < 0 || nj > m || nj < 0) continue;
                int q = id (ni, nj);
                add_edge (p + k * sum, q + k * sum, A);
                add_edge (p + 5 * sum, q + 5 * sum, C);
            }
        }
    }
    dijkstra ();
    int ans = INF;
    for (int i = 0; i < 6; i++) {
        ans = min (ans, dis [id (pt[t].F, pt[t].S) + i * sum]);
    }

    cout << ans << "\n";
} 
 
signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        init();
        solve();
    }
} 

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