JOI本選過去問 第8回 日本情報オリンピック本選 5問目 認証レベル

なんとか通りました。

つかれた。

問題文はこちら

世界スパッゲッティソース大会で決勝にいけそうなソースです。

joi本選の練習も兼ねて、mapとかvectorとかqueueとかpairとかいろんなの使ってみました。
なのでとても複雑になってしまった。。。

実行時間もそこまで遅くないから良いのではないかな？

解説読んでないからもっといい解法あるかも。

僕の解法についてはちょっと今疲れたので後で書きます。

計算量はlogとかいっぱい出てきてO(R nazo R)です。

#include <cstdio>
#include <queue>
#include <map>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> P;

int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

int r,w1,w2,h1,h2,x1,x2,y1,y2;


int k1[503][503];

int k2[503][503];

bool f1[503][503];

bool f2[503][503];



int main(){

  while(1){

  scanf("%d",&r);

  if(r == 0) break;
scanf("%d%d%d%d",&w1,&h1,&x1,&y1);

  for(int i = 1;i <= h1;i++){
    for(int j = 1;j <= w1;j++){
      scanf("%d",&k1[i][j]);
      f1[i][j] = true;
    }
  }

  scanf("%d%d%d%d",&w2,&h2,&x2,&y2);

  for(int i = 1;i <= h2;i++){
    for(int j = 1;j <= w2;j++){
      scanf("%d",&k2[i][j]);
      f2[i][j] = true;
    }
  }



  priority_queue< P, vector<P> , greater<P> > que;

  que.push(P(1,w1*(y1-1)+x1));

  f1[y1][x1] = false;

  map<int,int> m;

  int nl = 0,ko = 0;

  vector<int> hea;

  vector<int>::iterator it;



  while(!que.empty()){


    P tmp = que.top();
    que.pop();

    int fir = tmp.first;
    int sec = tmp.second;

    int xx = sec % w1;
    if(xx == 0) xx = w1;
    int yy = (sec / w1) + 1;
    f1 [yy][xx] = false; 

    for(int i = 0;i < 4;i++){
      int nx = dx[i] + xx;
      int ny = dy[i] + yy;

      if(nx >= 1 && nx <= w1 && ny >= 1 && ny <= h1 && f1[ny][nx] == true){
	que.push(P(k1[ny][nx],w1*(ny-1)+nx));
	f1[ny][nx] = false;
      }
    }

    if(nl < fir){
      hea.push_back(ko);
      m[ko] = nl;


      nl =max(nl,fir);
    }
    ko++;

  }
  hea.push_back(ko);
  m[ko] = nl;
 sort(hea.begin(),hea.end());



 que.push(P(1,w2*(y2-1)+x2));

 it = lower_bound(hea.begin(),hea.end(),r);


 int tuka = *it;

 int ans = m[tuka];
 if(ans == 0) ans = 1000000;


 f2[y2][x2] = false;

 int nau = 0;

 nl = 0;

 while(!que.empty()){

   P  tmp = que.top(); que.pop();

   int   fir = tmp.first;
   int  sec = tmp.second;

   int   xx = sec % w2;
    if(xx == 0) xx = w2;
    int   yy = (sec / w2);
    if(sec % w2 != 0) yy++;
    f2[yy][xx] = false; 

    for(int i = 0;i < 4;i++){
      int nx = dx[i] + xx;
      int ny = dy[i] + yy;

      if(nx >= 1 && nx <= w2 && ny >= 1 && ny <= h2 && f2[ny][nx] == true){
	que.push(P(k2[ny][nx],w2*(ny-1)+nx));
	f2[ny][nx] = false;
      }

    }




   if(nau >= r){
     ans = min(ans,nl);

     break;

   }
   if(nl != fir){
   int ttt = r - nau;

   it = lower_bound(hea.begin(),hea.end(),ttt);

   int sea = *it;

   int kari = m[sea];

   if(kari != 0){

   ans = min(ans,kari+nl);

   }

   nl = max(fir,nl);

   }

   nau++;
 
 }

 printf("%d\n",ans);

  }
 return 0;

}