oj.uz

Submission #685424

# Submission time Handle Problem Language Result Execution time Memory
685424 2023-01-24T10:39:40 Z coffee5427 Soccer (JOI17_soccer) C++17
5 / 100
 1517 ms 262144 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 246076 KB Output is correct
2 Correct 88 ms 241844 KB Output is correct
3 Correct 988 ms 258372 KB Output is correct
4 Correct 1048 ms 258524 KB Output is correct
5 Correct 384 ms 245988 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1517 ms 258328 KB Output is correct
2 Correct 1367 ms 258360 KB Output is correct
3 Correct 1008 ms 258344 KB Output is correct
4 Correct 1024 ms 258536 KB Output is correct
5 Correct 1025 ms 258528 KB Output is correct
6 Correct 1198 ms 258416 KB Output is correct
7 Runtime error 474 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 246076 KB Output is correct
2 Correct 88 ms 241844 KB Output is correct
3 Correct 988 ms 258372 KB Output is correct
4 Correct 1048 ms 258524 KB Output is correct
5 Correct 384 ms 245988 KB Output is correct
6 Correct 1517 ms 258328 KB Output is correct
7 Correct 1367 ms 258360 KB Output is correct
8 Correct 1008 ms 258344 KB Output is correct
9 Correct 1024 ms 258536 KB Output is correct
10 Correct 1025 ms 258528 KB Output is correct
11 Correct 1198 ms 258416 KB Output is correct
12 Runtime error 474 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -