Submission #159781

#	Time	Username	Problem	Language	Result	Execution time	Memory
159781		rama_pang	Wombats (IOI13_wombats)	C++14	100 / 100	9175 ms	192444 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24