Submission #885535

#	Time	Username	Problem	Language	Result	Execution time	Memory
885535		huutuan	Maze (JOI23_ho_t3)	C++14	94 / 100	2048 ms	781280 KiB

Main

#include<bits/stdc++.h>

using namespace std;

// #define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)(x).size())
#define sumof(x) accumulate(all(x), 0ll)

struct DisjointSetUnion{
   vector<int> lab, val;
 
   void init(int n){
      lab.assign(n+1, -1);
      val.assign(n+1, -1);
   }
 
   int find_set(int v){
      return lab[v]<0?v:lab[v]=find_set(lab[v]);
   }
 
   bool union_sets(int a, int b){
      a=find_set(a); b=find_set(b);
      if (a!=b){
         int new_val=val[a];
         if (lab[a]>lab[b]) swap(a, b);
         lab[a]+=lab[b];
         lab[b]=a;
         val[a]=new_val;
         val[b]=-1;
         return 1;
      }
      return 0;
   }
 
   int get_val(int x){
      return val[find_set(x)];
   }
};

struct LinkedList{
   int n;
   DisjointSetUnion prv, nxt;
   void init(int _n){
      n=_n;
      prv.init(n+1);
      nxt.init(n+1);
      for (int i=0; i<=n+1; ++i) prv.val[i]=i-1, nxt.val[i]=i+1;
   }
   void erase(int x){
      int t1=prv.get_val(x), t2=nxt.get_val(x);
      nxt.union_sets(x, t1);
      prv.union_sets(x, t2);
   }
   int get(int x){
      x=max(x, 0);
      return nxt.get_val(max(0, prv.get_val(x)));
   }
};

const int dx[]={1, -1, 0, 0, 1, 1, -1, -1}, dy[]={0, 0, 1, -1, 0, 1, -1, 1, -1};
int n, r, c;
int sr, sc, gr, gc;

void solve(){
   cin >> r >> c >> n;
   cin >> sr >> sc >> gr >> gc;
   vector<vector<char>> a(r+1, vector<char>(c+1));
   vector<vector<int>> dist(r+1, vector<int>(c+1, 1e9));
   vector<vector<int>> vis(r+1, vector<int>(c+1));
   vector<LinkedList> lr(r+1), lc(c+1);
   for (int i=1; i<=r; ++i) lr[i].init(c);
   for (int i=1; i<=c; ++i) lc[i].init(r);
   for (int i=1; i<=r; ++i) for (int j=1; j<=c; ++j) cin >> a[i][j];
   auto bfs_white=[&](vector<pair<int, int>> roots, int distance) -> vector<pair<int, int>> {
      queue<pair<int, int>> q;
      vector<pair<int, int>> found;
      for (auto &i:roots) q.emplace(i.first, i.second), dist[i.first][i.second]=distance, lr[i.first].erase(i.second), lc[i.second].erase(i.first);
      while (q.size()){
         int u=q.front().first, v=q.front().second;
         q.pop();
         for (int i=0; i<4; ++i){
            int x=u+dx[i], y=v+dy[i];
            if (x<1 || y<1 || x>r || y>c || dist[x][y]<1e9) continue;
            if (a[x][y]=='.'){
               dist[x][y]=distance;
               lr[x].erase(y);
               lc[y].erase(x);
               q.emplace(x, y);
            }else if (!vis[x][y]){
               vis[x][y]=1;
               found.emplace_back(x, y);
            }
         }
      }
      return found;
   };
   auto bfs_black=[&](vector<pair<int, int>> roots, int distance) -> vector<pair<int, int>> {
      vector<pair<int, int>> found;
      queue<pair<pair<int, int>, int>> q;
      for (auto &i:roots) q.push({i, 0});
      while (q.size()){
         int u=q.front().first.first, v=q.front().first.second, d=q.front().second;
         q.pop();
         if (d==3) continue;
         if ((d&1)==0){
            for (int y=lr[u].get(v-n+1); y!=c+1; y=lr[u].nxt.get_val(y)){
               int x=u;
               if (y-v>=n) break;
               q.push({{x, y}, d|1});
               dist[x][y]=distance;
               found.emplace_back(x, y);
               lc[y].erase(x);
               lr[x].erase(y);
            }
         }
         if ((d&2)==0){
            for (int x=lc[v].get(u-n+1); x!=r+1; x=lc[v].nxt.get_val(x)){
               int y=v;
               if (x-u>=n) break;
               q.push({{x, y}, d|2});
               dist[x][y]=distance;
               found.emplace_back(x, y);
               lc[y].erase(x);
               lr[x].erase(y);
            }
         }
      }
      return found;
   };
   int cur=0;
   vector<pair<int, int>> roots{{sr, sc}};
   while (dist[gr][gc]>=1e9){
      bfs_white(roots, cur).swap(roots);
      bfs_black(roots, ++cur).swap(roots);
   }
   cout << dist[gr][gc];
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 0 / 6