oj.uz

Submission #57486

# Submission time Handle Problem Language Result Execution time Memory
57486 2018-07-15T07:23:52 Z 강태규(#1669) Wall (CEOI14_wall) C++11
100 / 100
 629 ms 61828 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const llong inf = 1e16;
int n, m;
int grid[405][405];
int vert[405][405];
int horz[405][405];
bool res[405][405];
bool vertUsed[405][405];
bool horzUsed[405][405];
int pr[405 * 405];

struct _edge {
    int x, c;
    _edge(int x) : x(x), c(0) {}
    _edge(int x, int c) : x(x), c(c) {}
};

vector<_edge> edge[401 * 401 * 4];
llong dist[401 * 401 * 4];

int getNode1(int x, int y) {
    return x * (m + 1) + y;
}

struct node {
    int x;
    llong c;
    node(int x, llong c) : x(x), c(c) {}
    bool operator<(const node &p) const {
        return c > p.c;
    }
};

void dijkstra(int s, int n) {
    for (int i = 0; i < n; ++i) dist[i] = inf;
    priority_queue<node> pq;
    pq.emplace(s, dist[s] = 0);
    while (!pq.empty()) {
        node x = pq.top();
        pq.pop();
        if (x.c != dist[x.x]) continue;
        for (_edge i : edge[x.x]) {
            llong d = x.c + i.c;
            if (d < dist[i.x]) {
                pq.emplace(i.x, dist[i.x] = d);
                pr[i.x] = x.x;
            }
        }
    }
}

void connect(int x, int y) {
    int x1, y1, x2, y2;
    x1 = x / (m + 1);
    y1 = x % (m + 1);
    x2 = y / (m + 1);
    y2 = y % (m + 1);
    if (x1 > x2 || y1 > y2) {
        swap(x1, x2);
        swap(y1, y2);
    }
    if (x1 == x2) horzUsed[x2][y2] = 1;
    else vertUsed[x2][y2] = 1;
}

int main() {
    scanf("%d%d", &n, &m);
    vertUsed[0][0] = 1;
    horzUsed[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", grid[i] + j);
            if (grid[i][j] == 1) {
                res[i - 1][j - 1] = 1;
                res[i - 1][j] = 1;
                res[i][j - 1] = 1;
                res[i][j] = 1;
                
                vertUsed[i][j - 1] = 1;
                vertUsed[i][j] = 1;
                
                horzUsed[i - 1][j] = 1;
                horzUsed[i][j] = 1;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            scanf("%d", vert[i] + j);
            int a = getNode1(i - 1, j);
            int b = getNode1(i, j);
            edge[a].emplace_back(b, vert[i][j]);
            edge[b].emplace_back(a, vert[i][j]);
        }
    }
    for (int i = 0; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", horz[i] + j);
            int a = getNode1(i, j - 1);
            int b = getNode1(i, j);
            edge[a].emplace_back(b, horz[i][j]);
            edge[b].emplace_back(a, horz[i][j]);
        }
    }
    
    dijkstra(0, (n + 1) * (m + 1));
    
    {
        priority_queue<pll> pq;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                if (res[i][j]) {
                    int x = getNode1(i, j);
                    pq.emplace(dist[x], x);
                }
            }
        }
        
        while (!pq.empty()) {
            int x = pq.top().second;
            pq.pop();
            if (x == 0) continue;
            connect(x, pr[x]);
            x = pr[x];
            int i = x / (m + 1);
            int j = x % (m + 1);
            if (res[i][j]) continue;
            res[i][j] = 1;
            pq.emplace(dist[x], x);
        }
    }
    
    for (int i = 0; i < (n + 1) * (m + 1); ++i) {
        edge[i].clear();
    }
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            int a = getNode1(i, j) << 2;
            int b = a | 1;
            int c = a | 2;
            int d = a | 3;
            if (!vertUsed[i][j]) {
                edge[a].emplace_back(b);
                edge[b].emplace_back(a);
            }
            
            if (!horzUsed[i][j]) {
                edge[a].emplace_back(c);
                edge[c].emplace_back(a);
            }
            
            if (!vertUsed[i + 1][j]) {
                edge[c].emplace_back(d);
                edge[d].emplace_back(c);
            }
            
            if (!horzUsed[i][j + 1]) {
                edge[b].emplace_back(d);
                edge[d].emplace_back(b);
            }
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            int a = getNode1(i, j) << 2;
            int b = a | 1;
            int c = getNode1(i - 1, j) << 2 | 2;
            int d = c | 1;
            edge[a].emplace_back(c, vert[i][j]);
            edge[c].emplace_back(a, vert[i][j]);
            
            edge[b].emplace_back(d, vert[i][j]);
            edge[d].emplace_back(b, vert[i][j]);
        }
    }
    
    for (int i = 0; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int a = getNode1(i, j) << 2;
            int b = getNode1(i, j - 1) << 2 | 1;
            int c = a | 2;
            int d = b | 2;
            edge[a].emplace_back(b, horz[i][j]);
            edge[b].emplace_back(a, horz[i][j]);
            
            edge[c].emplace_back(d, horz[i][j]);
            edge[d].emplace_back(c, horz[i][j]);
        }
    }
    
    dijkstra(1, (n + 1) * (m + 1) * 4);
    printf("%lld\n", dist[2]);
	return 0;
}

Compilation message

wall.cpp: In function 'int main()':
wall.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
wall.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", grid[i] + j);
             ~~~~~^~~~~~~~~~~~~~~~~~~
wall.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", vert[i] + j);
             ~~~~~^~~~~~~~~~~~~~~~~~~
wall.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", horz[i] + j);
             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15612 KB Output is correct
2 Correct 15 ms 15712 KB Output is correct
3 Correct 18 ms 15712 KB Output is correct
4 Correct 17 ms 15852 KB Output is correct
5 Correct 17 ms 15852 KB Output is correct
6 Correct 21 ms 16120 KB Output is correct
7 Correct 18 ms 16132 KB Output is correct
8 Correct 18 ms 16140 KB Output is correct
9 Correct 20 ms 16240 KB Output is correct
10 Correct 19 ms 16240 KB Output is correct
11 Correct 22 ms 16304 KB Output is correct
12 Correct 22 ms 16404 KB Output is correct
13 Correct 25 ms 16480 KB Output is correct
14 Correct 21 ms 16504 KB Output is correct
15 Correct 23 ms 16504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16540 KB Output is correct
2 Correct 22 ms 16556 KB Output is correct
3 Correct 20 ms 16648 KB Output is correct
4 Correct 24 ms 16648 KB Output is correct
5 Correct 23 ms 16648 KB Output is correct
6 Correct 25 ms 16648 KB Output is correct
7 Correct 21 ms 16656 KB Output is correct
8 Correct 22 ms 16672 KB Output is correct
9 Correct 23 ms 16692 KB Output is correct
10 Correct 24 ms 16708 KB Output is correct
11 Correct 21 ms 16732 KB Output is correct
12 Correct 21 ms 16756 KB Output is correct
13 Correct 22 ms 16900 KB Output is correct
14 Correct 19 ms 16900 KB Output is correct
15 Correct 20 ms 16900 KB Output is correct
16 Correct 21 ms 16900 KB Output is correct
17 Correct 21 ms 16900 KB Output is correct
18 Correct 21 ms 16900 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 27580 KB Output is correct
2 Correct 132 ms 27580 KB Output is correct
3 Correct 139 ms 27580 KB Output is correct
4 Correct 125 ms 27980 KB Output is correct
5 Correct 221 ms 40428 KB Output is correct
6 Correct 140 ms 40428 KB Output is correct
7 Correct 256 ms 42380 KB Output is correct
8 Correct 308 ms 42380 KB Output is correct
9 Correct 308 ms 42380 KB Output is correct
10 Correct 376 ms 42968 KB Output is correct
11 Correct 251 ms 44264 KB Output is correct
12 Correct 100 ms 44264 KB Output is correct
13 Correct 283 ms 44264 KB Output is correct
14 Correct 373 ms 54432 KB Output is correct
15 Correct 498 ms 56704 KB Output is correct
16 Correct 480 ms 56720 KB Output is correct
17 Correct 606 ms 60104 KB Output is correct
18 Correct 514 ms 61828 KB Output is correct
19 Correct 629 ms 61828 KB Output is correct
20 Correct 500 ms 61828 KB Output is correct