oj.uz

Submission #159779

# Submission time Handle Problem Language Result Execution time Memory
159779 2019-10-24T14:41:02 Z rama_pang Wombats (IOI13_wombats) C++14
76 / 100
 8135 ms 262148 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14328 KB Output is correct
2 Correct 17 ms 14328 KB Output is correct
3 Correct 86 ms 17144 KB Output is correct
4 Correct 16 ms 14328 KB Output is correct
5 Correct 15 ms 14300 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 12 ms 4600 KB Output is correct
5 Correct 12 ms 4344 KB Output is correct
6 Correct 13 ms 4344 KB Output is correct
7 Correct 12 ms 4344 KB Output is correct
8 Correct 11 ms 3960 KB Output is correct
9 Correct 11 ms 4344 KB Output is correct
10 Correct 11 ms 3960 KB Output is correct
11 Correct 85 ms 6788 KB Output is correct
12 Correct 12 ms 4472 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1890 ms 83564 KB Output is correct
2 Correct 1850 ms 81208 KB Output is correct
3 Correct 1904 ms 83708 KB Output is correct
4 Correct 1909 ms 83576 KB Output is correct
5 Correct 1829 ms 81400 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 7574 ms 83864 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 30 ms 28412 KB Output is correct
2 Correct 29 ms 28408 KB Output is correct
3 Correct 29 ms 28408 KB Output is correct
4 Correct 67 ms 29736 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1885 ms 83692 KB Output is correct
2 Correct 1831 ms 81236 KB Output is correct
3 Correct 1898 ms 83868 KB Output is correct
4 Correct 1911 ms 83576 KB Output is correct
5 Correct 1821 ms 81420 KB Output is correct
6 Correct 29 ms 28408 KB Output is correct
7 Correct 28 ms 28408 KB Output is correct
8 Correct 29 ms 28336 KB Output is correct
9 Correct 67 ms 29660 KB Output is correct
10 Correct 15 ms 14328 KB Output is correct
11 Correct 16 ms 14424 KB Output is correct
12 Correct 86 ms 17144 KB Output is correct
13 Correct 16 ms 14328 KB Output is correct
14 Correct 18 ms 14460 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 12 ms 4348 KB Output is correct
19 Correct 12 ms 4344 KB Output is correct
20 Correct 14 ms 4472 KB Output is correct
21 Correct 13 ms 4472 KB Output is correct
22 Correct 11 ms 3964 KB Output is correct
23 Correct 12 ms 4472 KB Output is correct
24 Correct 11 ms 3960 KB Output is correct
25 Correct 89 ms 6776 KB Output is correct
26 Correct 12 ms 4344 KB Output is correct
27 Correct 7503 ms 83868 KB Output is correct
28 Correct 8039 ms 115020 KB Output is correct
29 Correct 8135 ms 109880 KB Output is correct
30 Correct 8109 ms 109716 KB Output is correct
31 Correct 8114 ms 116848 KB Output is correct
32 Correct 3 ms 632 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1877 ms 83704 KB Output is correct
2 Correct 1828 ms 81168 KB Output is correct
3 Correct 1910 ms 83584 KB Output is correct
4 Correct 1969 ms 83580 KB Output is correct
5 Correct 1840 ms 81300 KB Output is correct
6 Correct 28 ms 28280 KB Output is correct
7 Correct 28 ms 28280 KB Output is correct
8 Correct 29 ms 28280 KB Output is correct
9 Correct 66 ms 29692 KB Output is correct
10 Correct 18 ms 14328 KB Output is correct
11 Correct 15 ms 14400 KB Output is correct
12 Correct 87 ms 17144 KB Output is correct
13 Correct 15 ms 14268 KB Output is correct
14 Correct 15 ms 14328 KB Output is correct
15 Runtime error 424 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -