Submission #556482

#	Time	Username	Problem	Language	Result	Execution time	Memory
556482		alextodoran	Wall (CEOI14_wall)	C++17	100 / 100	291 ms	22936 KiB

wall

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int D_MAX = 400;

const int U = 0, R = 1, D = 2, L = 3;
const int UL = 0, UR = 1, DR = 2, DL = 3;

int N, M;

bool village[D_MAX][D_MAX];

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int cost[D_MAX + 1][D_MAX + 1][4];
bool isPoint (int x, int y) {
    return (0 <= x && x <= N && 0 <= y && y <= M);
}

int backdir[D_MAX + 1][D_MAX + 1];

ll dist[D_MAX + 1][D_MAX + 1];
bool seen[D_MAX + 1][D_MAX + 1];
void minDistTree () {
    for (int x = 0; x <= N; x++) {
        for (int y = 0; y <= M; y++) {
            dist[x][y] = LLONG_MAX;
            seen[x][y] = false;
            backdir[x][y] = -1;
        }
    }
    priority_queue <tuple <ll, int, int>> q;

    dist[0][0] = 0;
    q.push(make_tuple(-dist[0][0], 0, 0));
    while (q.empty() == false) {
        ll d; int x, y; tie(d, x, y) = q.top();
        q.pop();
        if (seen[x][y] == true) {
            continue;
        }
        seen[x][y] = true;
        for (int dir = 0; dir < 4; dir++) {
            int x1 = x + dx[dir], y1 = y + dy[dir];
            if (isPoint(x1, y1) == true && dist[x][y] + cost[x][y][dir] < dist[x1][y1]) {
                backdir[x1][y1] = (dir + 2) % 4;
                dist[x1][y1] = dist[x][y] + cost[x][y][dir];
                q.push(make_tuple(-dist[x1][y1], x1, y1));
            }
        }
    }
}

bool edge[D_MAX + 1][D_MAX + 1][4];

void addEdge (int x, int y, int dir) {
    edge[x][y][dir] = true;
    edge[x + dx[dir]][y + dy[dir]][(dir + 2) % 4] = true;
}

ll cdist[D_MAX + 1][D_MAX + 1][4];
bool cseen[D_MAX + 1][D_MAX + 1][4];
ll solve () {
    for (int x = 0; x <= N; x++) {
        for (int y = 0; y <= M; y++) {
            for (int c = 0; c < 4; c++) {
                cdist[x][y][c] = LLONG_MAX;
                cseen[x][y][c] = false;
            }
        }
    }
    priority_queue <tuple <ll, int, int, int>> q;

    function <void (int, int, int, int, int, int, int)>
        update = [&] (int x1, int y1, int c1, int x2, int y2, int c2, int cost) {
        if (isPoint(x2, y2) == true && cdist[x1][y1][c1] + cost < cdist[x2][y2][c2]) {
            cdist[x2][y2][c2] = cdist[x1][y1][c1] + cost;
            q.push(make_tuple(-cdist[x2][y2][c2], x2, y2, c2));
        }
    };

    cdist[0][0][UL] = LLONG_MIN;
    cdist[0][0][UR] = 0;
    q.push(make_tuple(-cdist[0][0][UR], 0, 0, UR));
    while (q.empty() == false) {
        ll d; int x, y, c; tie(d, x, y, c) = q.top();
        q.pop();
        if (cseen[x][y][c] == true) {
            continue;
        }
        cseen[x][y][c] = true;
        if (edge[x][y][c] == false) {
            update(x, y, c, x, y, (c + 1) % 4, 0);
        }
        if (edge[x][y][(c + 3) % 4] == false) {
            update(x, y, c, x, y, (c + 3) % 4, 0);
        }
        update(x, y, c, x + dx[c], y + dy[c], (c + 3) % 4, cost[x][y][c]);
        update(x, y, c, x + dx[(c + 3) % 4], y + dy[(c + 3) % 4], (c + 1) % 4, cost[x][y][(c + 3) % 4]);
    }
    return cdist[0][0][DL];
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < M; y++) {
            cin >> village[x][y];
        }
    }
    for (int x = 0; x < N; x++) {
        for (int y = 0; y <= M; y++) {
            cin >> cost[x][y][D];
            cost[x + 1][y][U] = cost[x][y][D];
        }
    }
    for (int x = 0; x <= N; x++) {
        for (int y = 0; y < M; y++) {
            cin >> cost[x][y][R];
            cost[x][y + 1][L] = cost[x][y][R];
        }
    }

    minDistTree();
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < M; y++) {
            if (village[x][y] == true) {
                int x1 = x, y1 = y;
                while (backdir[x1][y1] != -1) {
                    int dir = backdir[x1][y1];
                    int x2 = x1 + dx[dir], y2 = y1 + dy[dir];
                    addEdge(x1, y1, dir);
                    x1 = x2; y1 = y2;
                }
                addEdge(x, y, R);
                addEdge(x, y, D);
                addEdge(x + 1, y, R);
                addEdge(x, y + 1, D);
            }
        }
    }

    cout << solve() << "\n";

    return 0;
}

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