Submission #159779

#	Time	Username	Problem	Language	Result	Execution time	Memory
159779		rama_pang	Wombats (IOI13_wombats)	C++14	76 / 100	8135 ms	262148 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint 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): observe that the grids
    are planar, thus if will always follow the requirements for Knuth's optimization.

    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.

*/

lint R, C;
lint H[5555][255], V[5555][255];

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

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

        node(bool upd = false, int block = 0) {
            paths.assign(C, vector<lint>(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<lint>> mid(C, vector<lint>(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];
            //         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];
            //             }
            //         }
            //     }
            // }

            for (int i = 0; i < C; i++) {
                for (int j = 0; j < C; j++) {
                    res.paths[i][j] = INF;
                    for (int k = 0; k < C; k++) {
                        res.paths[i][j] = min(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;
      ^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24