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; }