Submission #413684

#	Time	Username	Problem	Language	Result	Execution time	Memory
413684		iANikzad	Wall (CEOI14_wall)	C++14	100 / 100	478 ms	60968 KiB

wall

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();

typedef long long ll;
typedef long double ld;

const int maxn = 4e2 + 7;
const int mod = 1e9 + 7;
const int INF = 1e18 + 7;
const int mlog = 20;
const int SQ = 400;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int n, m;
int a[maxn][maxn];

int d[2][maxn][maxn];
int dis[maxn][maxn];

pii par[maxn][maxn];

int dp[maxn * maxn * 4];
vector<pii> adj[maxn * maxn * 4];

set<array<int, 3>> bad;
int mark[maxn][maxn];

int idx(int x,int y,int c) { return 4 * ((m + 1) * x + y) + c; }

void add_edge(int u,int v,int w){ adj[u].pb({v, w}), adj[v].pb({u, w}); }

void add_bad(pii a, pii b)
{
    if(a > b) swap(a, b);

    if(a.F + 1 == b.F) bad.insert({0,a.F,a.S});
    else bad.insert({1, a.F, a.S});
}

void dfs(int x,int y)
{
    if(mark[x][y]) return;
    mark[x][y] = true;

    pii p = par[x][y];
    add_bad(p, {x, y});

    dfs(p.F, p.S);
}

int get(int x,int y,int dir)
{
    if(dir == 0) return d[0][x][y];
    if(dir == 1) return d[1][x][y];
    if(dir == 2) return d[0][x - 1][y];
    if(dir == 3) return d[1][x][y - 1];
}

bool check(int x,int y) { return 0 <= x && x <= n && 0 <= y && y <= m;  }

void dij(int v)
{
    for(int i = 0;i <= n; i++) for(int j = 0; j <= m; j++) dis[i][j] = +INF;
    dis[0][0] = 0;

    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq; pq.push({0, {0, 0}});
    while(!pq.empty())
    {
        auto p = pq.top(); pq.pop();
        int w, x, y; w = p.F; tie(x, y) = p.S;

        if(w > dis[x][y]) continue;

        for(int i = 0; i < 4; i++)
        {
            int nx = dx[i] + x;
            int ny = dy[i] + y;

            if(!check(nx, ny)) continue;

            int nw = w + get(x, y, i);
            if(nw < dis[nx][ny])
            {
                par[nx][ny] = {x, y};
                dis[nx][ny] = nw;
                pq.push({dis[nx][ny], make_pair(nx, ny)});
            }
        }
    }
}

void prep()
{
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(a[i][j])
    {
        add_bad({i, j}, {i, j + 1});
        add_bad({i, j + 1}, {i + 1, j + 1});
        add_bad({i + 1, j}, {i + 1, j + 1});
        add_bad({i, j}, {i  + 1, j});

        dfs(i, j);
    }

    bad.insert({0, -1, 0}), bad.insert({1, 0, -1});
}

int32_t main()
{
    FAST;

    cin >> n >> m;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j];

    for(int i = 0; i < n; i++) for(int j = 0; j < m + 1; j++)
        cin >> d[0][i][j];

    for(int i = 0; i < n + 1; i++) for(int j = 0; j < m; j++)
        cin >> d[1][i][j];

    dij(0);
    prep();

    // fake edges
    for(int i = 0; i < n; i++) for(int j = 0; j < m + 1; j++)
        add_edge(idx(i, j, 2), idx(i + 1, j, 1), d[0][i][j]), add_edge(idx(i, j, 3), idx(i + 1, j, 0), d[0][i][j]);

    for(int i = 0; i < n + 1; i++) for(int j = 0; j < m; j++)
        add_edge(idx(i, j, 0), idx(i, j + 1, 1), d[1][i][j]), add_edge(idx(i, j, 3), idx(i, j + 1, 2), d[1][i][j]);

    for(int i = 0; i < n + 1; i++) for(int j = 0; j < m + 1; j++)
    {
        if (!bad.count({0,i,j})) add_edge(idx(i,j,2), idx(i,j,3),0);
        if (!bad.count({0,i-1,j})) add_edge(idx(i,j,0), idx(i,j,1),0);
        if (!bad.count({1,i,j})) add_edge(idx(i,j,0), idx(i,j,3),0);
        if (!bad.count({1,i,j-1})) add_edge(idx(i,j,1), idx(i,j,2),0);
    }

    for(int i = 0; i < maxn * maxn * 4; i++) dp[i] = +INF;

    priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push({dp[2] = 0, 2});

    while(!pq.empty())
    {
        auto p = pq.top(); pq.pop();
        int w, v; tie(w, v) = p;

        if(w > dp[v]) continue;

        for(pii ed : adj[v])
        {
            int we, u; tie(u, we) = ed;
            if(w + we < dp[u])
            {
                dp[u] = w + we;
                pq.push({dp[u], u});
            }
        }
    }

    cout << dp[0] << "\n";

    return 0;
}

Compilation message (stderr)

wall.cpp:18:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int INF = 1e18 + 7;
      |                 ~~~~~^~~
wall.cpp: In function 'int get(int, int, int)':
wall.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^

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