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

UnionFindとPriorityQueueと本選5番

UnionFindのコードを書けるようにした。

去年の本選5番はPriorityQueueを使う方法が想定されているが、UnionFindでも解ける(とhosがいってた)ので、試してみた。

PriorityQueueのコードも書いた。殆ど同じ。

#include <algorithm>
#include <climits>
#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

struct UF {
    vector<int> p;
    UF(){} UF(int n):p(n,-1){}
    int add(){p.push_back(-1);return p.size()-1;}
    int rt(int x){return p[x]<0 ? x : p[x]=rt(p[x]);}
    int eq(int a, int b){return rt(a)==rt(b);}
    int siz(int x){return -p[rt(x)];}
    void cat(int a, int b){
        a=rt(a);b=rt(b);
        if(a==b)return;
        if(p[a]<p[b])swap(a,b);
        p[b]+=p[a];
        p[a]=b;
    }
};

int r;
struct flr {
    int w,h,ex,ey;
    vector<pair<int, int> > m;
    flr() {
        scanf("%d%d%d%d", &w,&h,&ex,&ey);
        vector<vector<int> > rms(w, vector<int>(h));
        vector<pair<int, pair<int, int> > > rmlvl(w*h);
        UF uf(w*h);
        for(int y = 0; y < h; ++y) {
            for(int x = 0; x < w; ++x) {
                scanf("%d", &rms[x][y]);
                rmlvl[x*h+y] = make_pair(rms[x][y], make_pair(x, y));
            }
        }
        sort(rmlvl.begin(), rmlvl.end());
        m.push_back(make_pair(0, 0));
        for(int i = 0; i < (int)rmlvl.size(); ++i) {
            int lv=rmlvl[i].first;
            int x=rmlvl[i].second.first;
            int y=rmlvl[i].second.second;
            if(0<=x-1 && rms[x-1][y]<=lv) uf.cat(x*h+y, (x-1)*h+y);
            if(0<=y-1 && rms[x][y-1]<=lv) uf.cat(x*h+y, x*h+(y-1));
            if(x+1<w && rms[x+1][y]<=lv) uf.cat(x*h+y, (x+1)*h+y);
            if(y+1<h && rms[x][y+1]<=lv) uf.cat(x*h+y, x*h+(y+1));
            m.push_back(make_pair(lv, uf.siz((ex-1)*h+(ey-1))));
        }
    }
};

int main(int argc, char **argv)
{
    scanf("%d", &r);
    flr f1;
    flr f2;
    int i1=0;
    int i2=f2.m.size()-1;
    int minsum=INT_MAX;
    while(i1<(int)f1.m.size() && 0<=i2) {
        if(f1.m[i1].second+f2.m[i2].second >= r) {
            minsum=min(minsum, f1.m[i1].first+f2.m[i2].first);
            i2--;
        } else {
            i1++;
        }
    }
    printf("%d\n", minsum);
    return 0;
}
#include <algorithm>
#include <climits>
#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

int r;
struct flr {
    int w,h,ex,ey;
    vector<pair<int, int> > m;
    flr() {
        scanf("%d%d%d%d", &w,&h,&ex,&ey);
        vector<vector<int> > rms(w, vector<int>(h));
        priority_queue<pair<int, pair<int, int> > > rmlvl;
        m.push_back(make_pair(0, 0));
        for(int y = 0; y < h; ++y) {
            for(int x = 0; x < w; ++x) {
                scanf("%d", &rms[x][y]);
            }
        }
        rmlvl.push(make_pair(-rms[ex-1][ey-1], make_pair(ex-1, ey-1)));
        rms[ex-1][ey-1]=0;
        int siz = 0;
        int lv_max = 0;
        while(!rmlvl.empty()) {
            int lv=-rmlvl.top().first;
            int x=rmlvl.top().second.first;
            int y=rmlvl.top().second.second;
            lv_max = max(lv_max, lv);
            rmlvl.pop();
            if(0<=x-1 && rms[x-1][y]) {
                rmlvl.push(make_pair(-rms[x-1][y], make_pair(x-1, y)));
                rms[x-1][y]=0;
            }
            if(x+1<w && rms[x+1][y]) {
                rmlvl.push(make_pair(-rms[x+1][y], make_pair(x+1, y)));
                rms[x+1][y]=0;
            }
            if(0<=y-1 && rms[x][y-1]) {
                rmlvl.push(make_pair(-rms[x][y-1], make_pair(x, y-1)));
                rms[x][y-1]=0;
            }
            if(y+1<h && rms[x][y+1]) {
                rmlvl.push(make_pair(-rms[x][y+1], make_pair(x, y+1)));
                rms[x][y+1]=0;
            }
            siz++;
            m.push_back(make_pair(lv_max, siz));
        }
    }
};

int main(int argc, char **argv)
{
    scanf("%d", &r);
    flr f1;
    flr f2;
    int i1=0;
    int i2=f2.m.size()-1;
    int minsum=INT_MAX;
    while(i1<(int)f1.m.size() && 0<=i2) {
        if(f1.m[i1].second+f2.m[i2].second >= r) {
            minsum=min(minsum, f1.m[i1].first+f2.m[i2].first);
            i2--;
        } else {
            i1++;
        }
    }
    printf("%d\n", minsum);
    return 0;
}