oj.uz

Submission #159781

# Submission time Handle Problem Language Result Execution time Memory
159781 2019-10-24T15:01:35 Z rama_pang Wombats (IOI13_wombats) C++14
100 / 100
 9175 ms 192444 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
/*  Use segment tree, each node all C * C answers of interval l...r.
    For query, it can be answered in O(1) by querying the root, V1 and V2

    To merge, done naively is O(C * C * C). However, observe that we can
    apply Knuth's optimization to make it O(C * C): uf we root i, then j
    is always increasing.

    Also, O(R * C * C) memory is too large, thus we can decompose the grid into
    blocks of a certain size, then build a segment tree of those blocks. To update
    a block, just brute force it.

*/

int R, C;
int H[5005][205], V[5005][205];

const int BLOCK_SIZE = 20;
const int BLOCK_COUNT = (5005 / BLOCK_SIZE);

struct segment_tree {
    struct node {
        vector<vector<int>> paths;

        node(bool upd = false, int block = 0) {
            paths.assign(C, vector<int>(C, INF));
            if (!upd) return;

            for (int i = 0; i < C; i++) {
                paths[i][i] = 0;
                for (int k = block * BLOCK_SIZE; k < (block + 1) * BLOCK_SIZE; k++) {
                    if (k >= R) continue;
                    for (int j = 1; j < C; j++) {
                        paths[i][j] = min(paths[i][j], paths[i][j - 1] + H[k][j - 1]); 
                    }
                    
                    for (int j = C - 2; j >= 0; j--) {
                        paths[i][j] = min(paths[i][j], paths[i][j + 1] + H[k][j]);
                    }

                    for (int j = 0; j < C; j++) {
                        paths[i][j] += V[k][j];
                    }
                }
            }
        }

        node merge(node a, node b) {
            node res;
            vector<vector<int>> mid(C, vector<int>(C, 0));

            for (int len = 0; len < C; len++) {
                for (int i = 0; i + len < C; i++) {
                    int j = i + len;
                    res.paths[i][j] = INF;

                    if (len == 0) {
                        for (int k = 0; k < C; k++) {
                            if (res.paths[i][j] > a.paths[i][k] + b.paths[k][j]) {
                                mid[i][j] = k;
                                res.paths[i][j] = a.paths[i][k] + b.paths[k][j];
                            }
                        }
                        continue;
                    }

                    /* DP Knuth's optimization, computing paths for new interval */
                    int le = mid[i][j - 1], ri = mid[i + 1][j];
                    assert(le <= ri);
                    for (int k = le; k <= ri; k++) {
                        if (res.paths[i][j] > a.paths[i][k] + b.paths[k][j]) {
                            mid[i][j] = k;
                            res.paths[i][j] = a.paths[i][k] + b.paths[k][j];
                        }
                    }
                }
            }

            /* Now in reverse, to handle case i > j */
            for (int len = 0; len < C; len++) {
                for (int i = C - 1; i - len >= 0; i--) {
                    int j = i - len;
                    res.paths[i][j] = INF;

                    if (len == 0) {
                        for (int k = 0; k < C; k++) {
                            if (res.paths[i][j] > a.paths[i][k] + b.paths[k][j]) {
                                mid[i][j] = k;
                                res.paths[i][j] = a.paths[i][k] + b.paths[k][j];
                            }
                        }
                        continue;
                    }

                    /* DP Knuth's optimization, computing paths for new interval */
                    int le = mid[i][j + 1], ri = mid[i - 1][j];
                    for (int k = le; k >= ri; k--) {
                        if (res.paths[i][j] > a.paths[i][k] + b.paths[k][j]) {
                            mid[i][j] = k;
                            res.paths[i][j] = a.paths[i][k] + b.paths[k][j];
                        }
                    }
                }
            }

            return res;
        }

    };

    vector<node> tree;

    inline int query(int v1, int v2) {
        return tree[1].paths[v1][v2];
    }

    void update(int n, int tl, int tr, int p) {
        if (tl == tr) {
            tree[n] = node(true, tl);
            return;
        }

        int mid = (tl + tr) / 2;
        if (p <= mid) 
            update(n * 2, tl, mid, p);
        else 
            update(n * 2 + 1, mid + 1, tr, p);
        
        tree[n] = tree[n].merge(tree[n * 2], tree[n * 2 + 1]);
    }

    void build(int n, int tl, int tr) {
        if (tl == tr) {
            tree[n] = node(true, tl);
            return;
        }

        int mid = (tl + tr) / 2;
        build(n * 2, tl, mid), build(n * 2 + 1, mid + 1, tr);
        tree[n] = tree[n].merge(tree[n * 2], tree[n * 2 + 1]);
    }

    void init() {
        tree.clear();
        tree.resize(4 * BLOCK_COUNT);
        build(1, 0, BLOCK_COUNT - 1);
    }

} seg;

void init(int R, int C, int h[5000][200], int v[5000][200]) {
    ::R = R, ::C = C;
    
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C - 1; j++) {
            H[i][j] = h[i][j];
        }
    }
    
    for (int i = 0; i < R - 1; i++) {
        for (int j = 0; j < C; j++) {
            V[i][j] = v[i][j];
        }
    }

    seg.init();
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    seg.update(1, 0, BLOCK_COUNT - 1, P / BLOCK_SIZE);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    seg.update(1, 0, BLOCK_COUNT - 1, P / BLOCK_SIZE);   
}

int escape(int V1, int V2) {
    return seg.query(V1, V2);
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
wombats.cpp: In constructor 'segment_tree::node::node(bool, int)':
wombats.cpp:184:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:184:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:184:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:184:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:184:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:184:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:28:9: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
         node(bool upd = false, int block = 0) {
         ^~~~
wombats.cpp:28:9: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:28:9: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp: In member function 'void segment_tree::build(int, int, int)':
wombats.cpp:135:10: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
     void build(int n, int tl, int tr) {
          ^~~~~
wombats.cpp:135:10: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:135:10: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp: In member function 'void segment_tree::update(int, int, int, int)':
wombats.cpp:120:10: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
     void update(int n, int tl, int tr, int p) {
          ^~~~~~
wombats.cpp:120:10: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:120:10: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8440 KB Output is correct
2 Correct 11 ms 8312 KB Output is correct
3 Correct 82 ms 10616 KB Output is correct
4 Correct 13 ms 8440 KB Output is correct
5 Correct 11 ms 8312 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 408 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 8 ms 2808 KB Output is correct
5 Correct 8 ms 2808 KB Output is correct
6 Correct 8 ms 2808 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 8 ms 2680 KB Output is correct
9 Correct 8 ms 2808 KB Output is correct
10 Correct 11 ms 2680 KB Output is correct
11 Correct 86 ms 4472 KB Output is correct
12 Correct 8 ms 2808 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 44056 KB Output is correct
2 Correct 400 ms 43736 KB Output is correct
3 Correct 417 ms 44092 KB Output is correct
4 Correct 443 ms 44152 KB Output is correct
5 Correct 409 ms 43640 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 1604 ms 44160 KB Output is correct
10 Correct 3 ms 632 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16376 KB Output is correct
2 Correct 20 ms 16376 KB Output is correct
3 Correct 20 ms 16376 KB Output is correct
4 Correct 58 ms 17912 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 44024 KB Output is correct
2 Correct 390 ms 43592 KB Output is correct
3 Correct 414 ms 44160 KB Output is correct
4 Correct 415 ms 44024 KB Output is correct
5 Correct 419 ms 43636 KB Output is correct
6 Correct 20 ms 16376 KB Output is correct
7 Correct 19 ms 16376 KB Output is correct
8 Correct 20 ms 16376 KB Output is correct
9 Correct 60 ms 17812 KB Output is correct
10 Correct 11 ms 8312 KB Output is correct
11 Correct 11 ms 8440 KB Output is correct
12 Correct 82 ms 11120 KB Output is correct
13 Correct 11 ms 8312 KB Output is correct
14 Correct 11 ms 8440 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 8 ms 2808 KB Output is correct
19 Correct 8 ms 2808 KB Output is correct
20 Correct 8 ms 2808 KB Output is correct
21 Correct 8 ms 2808 KB Output is correct
22 Correct 7 ms 2680 KB Output is correct
23 Correct 8 ms 2808 KB Output is correct
24 Correct 8 ms 2680 KB Output is correct
25 Correct 85 ms 4264 KB Output is correct
26 Correct 8 ms 2808 KB Output is correct
27 Correct 1603 ms 44124 KB Output is correct
28 Correct 2108 ms 63096 KB Output is correct
29 Correct 2168 ms 60060 KB Output is correct
30 Correct 2250 ms 60072 KB Output is correct
31 Correct 2193 ms 63884 KB Output is correct
32 Correct 3 ms 636 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 44152 KB Output is correct
2 Correct 390 ms 43640 KB Output is correct
3 Correct 414 ms 44024 KB Output is correct
4 Correct 417 ms 44180 KB Output is correct
5 Correct 414 ms 43512 KB Output is correct
6 Correct 21 ms 16376 KB Output is correct
7 Correct 19 ms 16376 KB Output is correct
8 Correct 20 ms 16376 KB Output is correct
9 Correct 58 ms 17784 KB Output is correct
10 Correct 11 ms 8312 KB Output is correct
11 Correct 11 ms 8324 KB Output is correct
12 Correct 82 ms 11180 KB Output is correct
13 Correct 11 ms 8312 KB Output is correct
14 Correct 11 ms 8440 KB Output is correct
15 Correct 2264 ms 191324 KB Output is correct
16 Correct 9159 ms 192444 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 3 ms 504 KB Output is correct
20 Correct 9 ms 2808 KB Output is correct
21 Correct 9 ms 2808 KB Output is correct
22 Correct 8 ms 2808 KB Output is correct
23 Correct 8 ms 2808 KB Output is correct
24 Correct 8 ms 2680 KB Output is correct
25 Correct 8 ms 2808 KB Output is correct
26 Correct 9 ms 2680 KB Output is correct
27 Correct 85 ms 5112 KB Output is correct
28 Correct 9 ms 2808 KB Output is correct
29 Correct 1600 ms 44048 KB Output is correct
30 Correct 2119 ms 63768 KB Output is correct
31 Correct 8728 ms 189840 KB Output is correct
32 Correct 8813 ms 190012 KB Output is correct
33 Correct 2177 ms 60536 KB Output is correct
34 Correct 8696 ms 186508 KB Output is correct
35 Correct 2249 ms 60668 KB Output is correct
36 Correct 8960 ms 186456 KB Output is correct
37 Correct 2183 ms 65296 KB Output is correct
38 Correct 8573 ms 190488 KB Output is correct
39 Correct 3 ms 632 KB Output is correct
40 Correct 9175 ms 186772 KB Output is correct