Submission #1124952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124952		TrendBattles	Wall (CEOI14_wall)	C++17	100 / 100	374 ms	62340 KiB

wall

#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;

#define INFILE "steelwall.inp"
#define OUTFILE "steelwall.out"

const int MAX_N = 410;
lli dist[MAX_N * MAX_N * 4 + 10];
vector <pair <int, int>> graph[MAX_N * MAX_N * 4 + 10];

int resident[MAX_N][MAX_N];
int row_cost[MAX_N][MAX_N], col_cost[MAX_N][MAX_N];

void add_edge(int u, int v, int w) {
    graph[u].emplace_back(v, w);
    graph[v].emplace_back(u, w);
}


template <class T>
using MinHeap = priority_queue <T, vector <T>, greater <T>>;
int minimise(lli& x, lli y) {
    if (x > y) return x = y, true;
    return false;
}
void Dijkstra(int source) {
    memset(dist, 0x3f, sizeof dist);
    dist[source] = 0;

    MinHeap <pair <lli, int>> heap;
    heap.emplace(0, source);
    
    while (not heap.empty()) {
        lli d; int u; tie(d, u) = heap.top();
        heap.pop();
        if (d != dist[u]) continue;

        for (pair <int, int>& E : graph[u]) {
            int v, w; tie(v, w) = E;
            if (minimise(dist[v], dist[u] + w)) {
                heap.emplace(dist[v], v);
            }
        }
    }
}

void reset() {
    for (int i = 0; i <= MAX_N * MAX_N; ++i) {
        graph[i].clear();
        graph[i].shrink_to_fit();
    }
}

#define ID(i, j) ((i) * (M + 1) + (j))
int banned_down[MAX_N][MAX_N], banned_right[MAX_N][MAX_N];
int visited[MAX_N * MAX_N + 10];


int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen(INFILE, "r")) {
        freopen(INFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }

    int N, M; cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            cin >> resident[i][j];
        }
    }       

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= M; ++j) {
            cin >> row_cost[i][j];
            add_edge(ID(i, j), ID(i + 1, j), row_cost[i][j]);
        }
    }

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> col_cost[i][j];
            add_edge(ID(i, j), ID(i, j + 1), col_cost[i][j]);
        }
    }

    Dijkstra(0);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (resident[i][j]) {
                banned_down[i - 1][j - 1] = banned_down[i - 1][j] = banned_right[i - 1][j - 1] = banned_right[i][j - 1] = true;
            }
        }
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (not resident[i][j]) continue;

            queue <int> q;
            q.push(ID(i, j));

            while (not q.empty()) {
                int c_id = q.front(); q.pop();
                if (visited[c_id]) continue;

                visited[c_id] = true;
                if (c_id == 0) continue;

                for (pair <int, int>& E : graph[c_id]) {
                    int p_id, w; tie(p_id, w) = E;

                    if (dist[p_id] + w != dist[c_id]) continue;
                    q.push(p_id);

                    int x = c_id / (M + 1), y = c_id % (M + 1);
                    int u = p_id / (M + 1), v = p_id % (M + 1);

                    if (x + 1 == u) {
                        banned_down[x][y] = true;
                    }
                    if (x - 1 == u) {
                        banned_down[u][v] = true;
                    }
                    if (y + 1 == v) {
                        banned_right[x][y] = true;
                    }
                    if (y - 1 == v) {
                        banned_right[u][v] = true;
                    }

                    break;
                }
            }
        }
    }

    reset();
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= M; ++j) {
            for (int d = 0; d < 2; ++d) {
                add_edge(ID(i, j) * 4 + d + 2, ID(i + 1, j) * 4 + d, row_cost[i][j]);
            }

            if (not banned_down[i][j]) {
                add_edge(ID(i, j) * 4 + 2, ID(i, j) * 4 + 3, 0);
                add_edge(ID(i + 1, j) * 4 + 0, ID(i + 1, j) * 4 + 1, 0);
            }
        }
    }

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j < M; ++j) {
            for (int d : {1, 3}) {
                add_edge(ID(i, j) * 4 + d, ID(i, j + 1) * 4 + d - 1, col_cost[i][j]);
            }

            if (not banned_right[i][j]) {
                add_edge(ID(i, j) * 4 + 1, ID(i, j) * 4 + 3, 0);
                add_edge(ID(i, j + 1) * 4 + 0, ID(i, j + 1) * 4 + 2, 0);
            }
        }
    }

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            if (i == 0 and j == 0) continue;

            if (i == 0) {
                add_edge(ID(i, j) * 4 + 0, ID(i, j) * 4 + 1, 0);
            }
            if (i == N) {
                add_edge(ID(i, j) * 4 + 2, ID(i, j) * 4 + 3, 0);
            }
            if (j == 0) {
                add_edge(ID(i, j) * 4 + 0, ID(i, j) * 4 + 2, 0);
            }
            if (j == M) {
                add_edge(ID(i, j) * 4 + 1, ID(i, j) * 4 + 3, 0);
            }
        }
    }

    Dijkstra(ID(0, 0) * 4 + 1);
    cout << dist[ID(0, 0) * 4 + 2];
    return 0;
}

Compilation message (stderr)

wall.cpp: In function 'int main()':
wall.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
wall.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40