Submission #1105448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105448		duckindog	Maze (JOI23_ho_t3)	C++17	86 / 100	2048 ms	564024 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

struct DSU { 
  vector<int> id;
  DSU(int n) : id(n, -1) {}
  int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
  void add(int u, int v) { 
    u = root(u); v = root(v);
    if (u == v) return;
    id[u] += id[v];
    id[v] = u;
  }
};

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  int r, c, n; cin >> r >> c >> n;
  int Sr, Sc; cin >> Sr >> Sc;
  int Gr, Gc; cin >> Gr >> Gc;

  vector<vector<char>> a(r + 10, vector<char>(c + 10));
  for (int i = 1; i <= r; ++i) { 
    for (int j = 1; j <= c; ++j) cin >> a[i][j];
  }
  auto in = [&](int x, int y) { return 1 <= x && x <= r && 1 <= y && y <= c; };

  vector<DSU> R(r + 10, DSU(c + 10));
  vector<DSU> C(c + 10, DSU(r + 10));
  
  vector<vector<int>> f(r + 10, vector<int>(c + 10, 1'000'000'000));
  deque<pair<int, int>> q;
  q.push_back({Sr, Sc});
  f[Sr][Sc] = 0;
  while (q.size()) { 
    auto [x, y] = q.front(); q.pop_front();
    auto add = [&](int nX, int nY, int w) { 
      if (f[nX][nY] > f[x][y] + w) { 
        f[nX][nY] = f[x][y] + w;

        if (w) q.push_back({nX, nY});
        else q.push_front({nX, nY});
      }
    };

    for (int t = 0; t < 4; ++t) { 
      int nX = x + dx[t], nY = y + dy[t];
      if (!in(nX, nY) || a[nX][nY] == '#') continue;
      add(nX, nY, 0);
    }

    { //add a fricking regtangle
      int stX = max(1, x - n + 1), edX = min(r, x + n - 1);
      int stY = max(1, y - n), edY = min(c, y + n);
      
      for (int h = stX; h <= edX; h = C[stY].root(h)) {
        add(h, stY, 1);  
        for (int i = R[h].root(stY); i < edY; i = R[h].root(i)) {
          R[h].add(R[h].root(i) + 1, R[h].root(i));
          add(h, R[h].root(i), 1);
        }
        if (R[h].root(stY) - stY >= 2 * n + 1 || R[h].root(stY) == c) C[stY].add(h + 1, h);
        h += 1;
      }
    }

    { //add 2 fricking strips due to the rectangle is not the fucking square
      int stX = max(1, x - n), edX = min(r, x + n);
      int stY = max(1, y - n + 1), edY = min(c, y + n - 1);
      
      for (int type = 0; type < 2; ++type) { 
        int h = (!type ? stX : edX);
        
        add(h, stY, 1);
        for (int i = R[h].root(stY); i < edY; i = R[h].root(i)) {
          R[h].add(R[h].root(i) + 1, R[h].root(i));
          add(h, R[h].root(i), 1);
        }
        if (R[h].root(stY) - stY >= 2 * n + 1 || R[h].root(stY) == c) C[stY].add(h + 1, h);
      }
    }
  }

  cout << f[Gr][Gc] << "\n";
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
}

• 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: 0 / 8
• Subtask 8: 0 / 6