oj.uz

Submission #413684

# Submission time Handle Problem Language Result Execution time Memory
413684 2021-05-29T08:56:15 Z iANikzad Wall (CEOI14_wall) C++14
100 / 100
 478 ms 60968 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18636 KB Output is correct
2 Correct 13 ms 18624 KB Output is correct
3 Correct 13 ms 18500 KB Output is correct
4 Correct 13 ms 18508 KB Output is correct
5 Correct 13 ms 18636 KB Output is correct
6 Correct 14 ms 19020 KB Output is correct
7 Correct 17 ms 19020 KB Output is correct
8 Correct 16 ms 19020 KB Output is correct
9 Correct 16 ms 18832 KB Output is correct
10 Correct 15 ms 19020 KB Output is correct
11 Correct 15 ms 19136 KB Output is correct
12 Correct 19 ms 19272 KB Output is correct
13 Correct 16 ms 19228 KB Output is correct
14 Correct 22 ms 19280 KB Output is correct
15 Correct 15 ms 19100 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19276 KB Output is correct
2 Correct 16 ms 19256 KB Output is correct
3 Correct 18 ms 19276 KB Output is correct
4 Correct 18 ms 19276 KB Output is correct
5 Correct 19 ms 19224 KB Output is correct
6 Correct 16 ms 19276 KB Output is correct
7 Correct 16 ms 19228 KB Output is correct
8 Correct 18 ms 19232 KB Output is correct
9 Correct 15 ms 19228 KB Output is correct
10 Correct 17 ms 19308 KB Output is correct
11 Correct 16 ms 19224 KB Output is correct
12 Correct 19 ms 19284 KB Output is correct
13 Correct 18 ms 19276 KB Output is correct
14 Correct 16 ms 19316 KB Output is correct
15 Correct 17 ms 19232 KB Output is correct
16 Correct 17 ms 19332 KB Output is correct
17 Correct 18 ms 19324 KB Output is correct
18 Correct 17 ms 19208 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 29228 KB Output is correct
2 Correct 91 ms 27360 KB Output is correct
3 Correct 90 ms 27840 KB Output is correct
4 Correct 105 ms 28452 KB Output is correct
5 Correct 209 ms 42392 KB Output is correct
6 Correct 114 ms 29004 KB Output is correct
7 Correct 304 ms 42468 KB Output is correct
8 Correct 225 ms 40520 KB Output is correct
9 Correct 194 ms 40416 KB Output is correct
10 Correct 247 ms 42064 KB Output is correct
11 Correct 264 ms 43876 KB Output is correct
12 Correct 105 ms 29360 KB Output is correct
13 Correct 233 ms 40004 KB Output is correct
14 Correct 361 ms 57108 KB Output is correct
15 Correct 382 ms 54596 KB Output is correct
16 Correct 378 ms 55460 KB Output is correct
17 Correct 452 ms 57952 KB Output is correct
18 Correct 478 ms 60968 KB Output is correct
19 Correct 466 ms 55912 KB Output is correct
20 Correct 385 ms 55364 KB Output is correct