/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 168ms 560.0 KiB
#2 Accepted 88ms 564.0 KiB
#3 Accepted 107ms 556.0 KiB
#4 Accepted 132ms 564.0 KiB
#5 Accepted 106ms 556.0 KiB
#6 Accepted 203ms 560.0 KiB
#7 Accepted 74ms 564.0 KiB
#8 Accepted 142ms 548.0 KiB
#9 Accepted 154ms 564.0 KiB
#10 Accepted 133ms 556.0 KiB
#11 Accepted 117ms 560.0 KiB
#12 Accepted 112ms 560.0 KiB
#13 Accepted 94ms 560.0 KiB
#14 Accepted 112ms 556.0 KiB
#15 Accepted 122ms 564.0 KiB
#16 Accepted 67ms 564.0 KiB
#17 Accepted 77ms 556.0 KiB
#18 Accepted 175ms 556.0 KiB
#19 Accepted 106ms 560.0 KiB
#20 Accepted 88ms 552.0 KiB
#21 Accepted 71ms 556.0 KiB
#22 Accepted 139ms 552.0 KiB
#23 Accepted 91ms 552.0 KiB
#24 Accepted 94ms 560.0 KiB
#25 Accepted 152ms 564.0 KiB
#26 Accepted 96ms 552.0 KiB
#27 Accepted 80ms 548.0 KiB
#28 Accepted 80ms 564.0 KiB
#29 Accepted 110ms 568.0 KiB
#30 Accepted 101ms 560.0 KiB
#31 Accepted 110ms 556.0 KiB
#32 Accepted 85ms 556.0 KiB
#33 Accepted 89ms 560.0 KiB
#34 Accepted 123ms 564.0 KiB
#35 Accepted 72ms 556.0 KiB
#36 Accepted 147ms 560.0 KiB
#37 Accepted 182ms 556.0 KiB
#38 Accepted 81ms 564.0 KiB
#39 Accepted 107ms 564.0 KiB
#40 Accepted 79ms 564.0 KiB
#41 Accepted 119ms 556.0 KiB
#42 Accepted 145ms 560.0 KiB
#43 Accepted 103ms 564.0 KiB
#44 Accepted 98ms 552.0 KiB
#45 Accepted 67ms 556.0 KiB
#46 Accepted 95ms 556.0 KiB
#47 Accepted 180ms 560.0 KiB
#48 Accepted 129ms 556.0 KiB
#49 Accepted 94ms 564.0 KiB
#50 Accepted 164ms 556.0 KiB
#51 Accepted 114ms 560.0 KiB
#52 Accepted 140ms 556.0 KiB
#53 Accepted 114ms 556.0 KiB
#54 Accepted 242ms 564.0 KiB
#55 Accepted 121ms 556.0 KiB
#56 Accepted 173ms 556.0 KiB
#57 Accepted 235ms 556.0 KiB
#58 Accepted 178ms 568.0 KiB
#59 Accepted 82ms 556.0 KiB
#60 Accepted 605ms 564.0 KiB
#61 Accepted 98ms 560.0 KiB
#62 Accepted 111ms 556.0 KiB
#63 Accepted 103ms 552.0 KiB
#64 Accepted 100ms 564.0 KiB
#65 Accepted 133ms 556.0 KiB
#66 Accepted 94ms 560.0 KiB
#67 Accepted 101ms 560.0 KiB
#68 Accepted 211ms 552.0 KiB
#69 Accepted 127ms 560.0 KiB
#70 Accepted 198ms 560.0 KiB
#71 Accepted 144ms 564.0 KiB
#72 Accepted 285ms 564.0 KiB
#73 Accepted 153ms 568.0 KiB
#74 Accepted 155ms 560.0 KiB
#75 Accepted 225ms 560.0 KiB
#76 Accepted 358ms 564.0 KiB
#77 Accepted 138ms 552.0 KiB
#78 Accepted 163ms 560.0 KiB
#79 Accepted 245ms 560.0 KiB
#80 Accepted 118ms 556.0 KiB
#81 Accepted 798ms 568.0 KiB
#82 Accepted 263ms 564.0 KiB
#83 Accepted 398ms 556.0 KiB
#84 Accepted 131ms 556.0 KiB
#85 Accepted 477ms 556.0 KiB
#86 Accepted 301ms 560.0 KiB
#87 Accepted 279ms 560.0 KiB
#88 Accepted 235ms 564.0 KiB
#89 Accepted 124ms 556.0 KiB
#90 Time Exceeded ≥1098ms ≥532.0 KiB
#91 Time Exceeded ≥1098ms ≥532.0 KiB

Code

#include<bits/stdc++.h>

using namespace std;

using field=array<array<int,11>,11>;

int dx4[4]={1,-1,0,0};
int dy4[4]={0,0,1,-1};

bool ins(int i,int j){
  return (0<=i && i<11 && 0<=j && j<11);
}

field inif;

int escape(int i,int j,int clk,field &a){
  if(a[i][j]<=clk){return -1;}
  field fie=inif;
  queue<pair<int,int>> qq;
  qq.push({i,j});
  fie[i][j]=clk;
  while(!qq.empty()){
    auto od=qq.front(); qq.pop();
    for(int k=0;k<4;k++){
      int x=od.first+dx4[k];
      int y=od.second+dy4[k];
      if(!ins(x,y)){continue;}
      int tt=fie[od.first][od.second]+1;
      if(fie[x][y]>5e8 && tt<a[x][y]){
        fie[x][y]=tt;
        qq.push({x,y});
      }
    }
  }

  int res=1e9;
  for(int i=0;i<11;i++){
    res=min(res,fie[i][0]);
    res=min(res,fie[i][10]);
    res=min(res,fie[0][i]);
    res=min(res,fie[10][i]);
  }
  if(res>5e8){res=-1;}
  return res;
}

int main(){
  for(int i=0;i<11;i++){
    for(int j=0;j<11;j++){
      inif[i][j]=1e9;
    }
  }

  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  field og=inif;
  vector<pair<int,int>> vp;
  queue<pair<int,int>> qq;
  for(int i=0;i<11;i++){
    for(int j=0;j<11;j++){
      string s;
      cin >> s;
      if(s=="#"){og[i][j]=1e9;}
      if(s=="P"){og[i][j]=1e9; vp.push_back({i,j});}
      if(s=="F"){og[i][j]=0; qq.push({i,j});}
    }
  }
  while(!qq.empty()){
    auto od=qq.front(); qq.pop();
    for(int i=0;i<4;i++){
      int x=od.first+dx4[i];
      int y=od.second+dy4[i];
      if(!ins(x,y)){continue;}
      if(og[x][y]>5e8){
        og[x][y]=og[od.first][od.second]+1;
        qq.push({x,y});
      }
    }
  }

  // for(auto &nx : og){
  //   for(auto &ny : nx){
  //     cout << ny << " ";
  //   }cout << "\n";
  // }

  int res=0;
  do{
    int cres=0;
    int clk=0;
    for(auto &nx : vp){
      int cc=escape(nx.first,nx.second,clk,og);
      // cout << cc << "\n";
      if(cc<0){break;}
      clk=(cc+1);
      cres++;
    }
    res=max(res,cres);
  }while(next_permutation(vp.begin(),vp.end()));
  cout << res << "\n";
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1221 G. Nine-eleven
Contest
Happy New Year 2026
Language
C++17 (G++ 13.2.0)
Submit At
2026-01-06 15:48:17
Judged At
2026-01-06 15:48:17
Judged By
Score
89
Total Time
≥1098ms
Peak Memory
≥568.0 KiB