oj.uz

답안 #159768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
159768 2019-10-24T13:46:43 Z rama_pang 웜뱃 (IOI13_wombats) C++14
9 / 100
 202 ms 8828 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

/*  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.

*/

int R, C;
vector<vector<int>> H, V;
const int BLOCK_SIZE = 20;
int BLOCK_COUNT;

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

        node(bool upd = false, int block = 0) {
            paths.assign(C, vector<int>(C, INT_MAX));
            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++) {
                        if (paths[i][j - 1] == INT_MAX) continue;
                        paths[i][j] = min(paths[i][j], paths[i][j - 1] + H[k][j - 1]); 
                    }
                    for (int j = C - 2; j >= 0; j--) {
                        if (paths[i][j + 1] == INT_MAX) continue;
                        paths[i][j] = min(paths[i][j], paths[i][j + 1] + H[k][j]);
                    }
                    
                    for (int j = 0; k < R - 1 && 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] = INT_MAX;

                    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;
    H.assign(R, vector<int>(C - 1, 0));
    V.assign(R - 1, vector<int>(C, 0));
    
    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];
        }
    }

    BLOCK_COUNT = (R / BLOCK_SIZE) + 1;
    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) {
    // cout << V1 << " " << 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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4728 KB Output is correct
2 Correct 9 ms 4728 KB Output is correct
3 Correct 82 ms 7544 KB Output is correct
4 Correct 10 ms 4772 KB Output is correct
5 Correct 10 ms 4728 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

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 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 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 202 ms 1656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 8828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 202 ms 1656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 202 ms 1648 KB Output isn't correct
2 Halted 0 ms 0 KB -