読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

Skew Heap

データ構造

Skew Heap は, meld (2 つのpriority queue をmerge する操作) ができるheapです.
meld ができると,
push は, 新しい要素をヒープとして親とmeld,
pop は 親の子をmeld

で実装できてしまいます.
計算量はならしO(log N) で便利です.
(くわしくはhos さんのブログ などを参照してください.)

これをつかって, AOJ 0542 (Authentication Level) を解いてみました. なかなか高速です.

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
struct Heap {
    Heap *l, *r;
    int val;
    int pos;
    Heap(int val, int pos) : val(val), pos(pos){
        l = r = (Heap *)0;
    }
};
 
Heap *root;
 
Heap *meld(Heap *a, Heap *b)
{
    if (!a) return (b);
    if (!b) return (a);
     
    if (a->val > b->val) swap(a, b);
    a->r = meld(a->r, b);
    swap(a->l, a->r);
     
    return (a);
}
 
void push(Heap x)
{
    Heap *p = new Heap(x);
     
    root = meld(root, p);
}
 
Heap top()
{
    return (*root);
}
 
void pop()
{
    Heap *p = root;
     
    root = meld(root->r, root->l);
    delete p;
}
 
int reqLevel[2][500 * 500 + 1];
int map[512][512];
bool visited[512][512];
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
 
int main()
{
    int R;
     
    while (scanf("%d", &R) && R){
         
        for (int t = 0; t < 2; t++){
            int W, H, Sx, Sy;
            scanf("%d %d %d %d", &W, &H, &Sx, &Sy);
             
            for (int i = 1; i <= R; i++){
                reqLevel[t][i] = 1000000000;
            }
             
            for (int i = 0; i < H; i++){
                for (int j = 0; j < W; j++){
                    scanf("%d", &map[i][j]);
                }
            }
             
            memset(visited, 0, sizeof(visited));
            --Sy; --Sx;
            push(Heap(map[Sy][Sx], Sy * 1000 + Sx));
            int req = 0;
            int num = 0;
            while (root){
                Heap x = top();
                pop();
                 
                if (visited[x.pos / 1000][x.pos % 1000]) continue;
                visited[x.pos / 1000][x.pos % 1000] = true;
                 
                req = max(req, x.val);
                reqLevel[t][++num] = req;
                 
                for (int i = 0; i < 4; i++){
                    int ny = x.pos / 1000 + dy[i], nx = x.pos % 1000 + dx[i];
                    if (0 <= ny && ny < H && 0 <= nx && nx < W){
                        push(Heap(map[ny][nx], ny * 1000 + nx));
                    }
                }
            }
        }
         
        int ans = 2000000000;
         
        for (int i = 0; i <= R; i++){
            ans = min(ans, reqLevel[0][i] + reqLevel[1][R - i]);
        }
         
        printf("%d\n", ans);
    }
     
    return (0);
}