Submission #1201374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201374		shadow_sami	Wombats (IOI13_wombats)	C++20	0 / 100	7 ms	15936 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

static const int B = 10;    // block size
static const int INF = 2e9;

int n, m;
int H[5000][200], Vv[5000][200];

// For Knuth optimization in merges
int opt_knuth[200][200];

// Each node stores an m×m matrix
using Mat = vector<array<int,200>>;

// Segment tree and mapping from block to leaf
vector<Mat> seg;
vector<int> which_leaf;

// Temporary matrices for building
Mat tmp1, tmp2;

// Build the single-row transfer matrix A from row i in O(m^2)
void build_row(int i, Mat &A) {
    for(int j = 0; j < m; ++j) {
        int sum = 0;
        // move east
        for(int k = j; k < m; ++k) {
            A[j][k] = sum + Vv[i][k];
            if (k+1 < m) sum += H[i][k];
        }
        sum = 0;
        // move west
        for(int k = j-1; k >= 0; --k) {
            sum += H[i][k];
            A[j][k] = sum + Vv[i][k];
        }
    }
}

// Knuth-optimized merge C = A ★ B in O(m^2)
void knuth_merge(const Mat &A, const Mat &B, Mat &C) {
    // init to INF
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < m; ++j)
            C[i][j] = INF;

    // traverse anti-diagonals
    for(int dif = -(m-1); dif <= m-1; ++dif) {
        int i0 = max(0, -dif);
        int j0 = i0 + dif;
        int len = min(m - i0, m - j0);
        for(int t = 0; t < len; ++t) {
            int i = i0 + t, j = j0 + t;
            int lo = (j>0    ? opt_knuth[i][j-1] : 0);
            int hi = (i+1<m  ? opt_knuth[i+1][j] : m-1);
            lo = max(lo, 0); hi = min(hi, m-1);

            int best_k = lo;
            int best_v = A[i][lo] + B[lo][j];
            for(int k = lo+1; k <= hi; ++k) {
                int v = A[i][k] + B[k][j];
                if (v < best_v) {
                    best_v = v;
                    best_k = k;
                }
            }
            C[i][j] = best_v;
            opt_knuth[i][j] = best_k;
        }
    }
}

// Build the block-transfer matrix for block b into node seg[node_id]
void build_block(int b, int node_id) {
    build_row(b*B, seg[node_id]);
    int end = min((b+1)*B, n);
    for(int i = b*B + 1; i < end; ++i) {
        build_row(i, tmp1);
        knuth_merge(seg[node_id], tmp1, tmp2);
        seg[node_id] = tmp2;
    }
}

// Build segment tree over blocks [l..r)
void build_tree(int node_id, int l, int r) {
    if (r - l == 1) {
        which_leaf[l] = node_id;
        build_block(l, node_id);
    } else {
        int mid = (l + r) >> 1;
        build_tree(2*node_id,     l,   mid);
        build_tree(2*node_id + 1, mid,  r);
        knuth_merge(seg[2*node_id], seg[2*node_id + 1], seg[node_id]);
    }
}

// Update block p (row i in block p has changed)
void update_tree(int node_id, int l, int r, int p) {
    if (r - l == 1) {
        build_block(p, node_id);
    } else {
        int mid = (l + r) >> 1;
        if (p < mid)
            update_tree(2*node_id,     l,   mid, p);
        else
            update_tree(2*node_id + 1, mid,  r,  p);
        knuth_merge(seg[2*node_id], seg[2*node_id + 1], seg[node_id]);
    }
}

// API

void init(int _n, int _m, int A[5000][200], int Bv[5000][200]) {
    n = _n; m = _m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j) {
            H[i][j]  = A[i][j];
            Vv[i][j] = Bv[i][j];
        }

    int blocks = (n + B - 1) / B;
    seg.resize(4 * blocks);
    which_leaf.assign(blocks, -1);

    tmp1.assign(m, array<int,200>());
    tmp2.assign(m, array<int,200>());

    build_tree(1, 0, blocks);
}

void changeH(int i, int j, int w) {
    H[i][j] = w;
    int b = i / B;
    update_tree(1, 0, (n+B-1)/B, b);
}

void changeV(int i, int j, int w) {
    Vv[i][j] = w;
    int b = i / B;
    update_tree(1, 0, (n+B-1)/B, b);
}

int escape(int v1, int v2) {
    // root at seg[1] holds full n-row transfer
    int ans = INF, sum = 0;
    for(int k = v2; k < m; ++k) {
        ans = min(ans, sum + seg[1][v1][k]);
        if(k+1 < m) sum += H[n-1][k];
    }
    sum = 0;
    for(int k = v2-1; k >= 0; --k) {
        sum += H[n-1][k];
        ans = min(ans, sum + seg[1][v1][k]);
    }
    return ans;
}

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