Submission #839450

#TimeUsernameProblemLanguageResultExecution timeMemory
839450dong_liuMaze (JOI23_ho_t3)C++17
100 / 100
1667 ms580420 KiB
#pragma GCC optimize("O3,unroll-loops") #include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) #endif const int NM = 6e6; typedef pair<int, int> pi; struct Range { int *p, n; char *rem; Range(int n) : n(n) { p = (int *) malloc(n * sizeof(int)); rem = (char *) malloc(n * sizeof(char)); for (int i = 0; i < n; i++) p[i] = i, rem[i] = false; } int dsf(int i) { return p[i] == i ? i : p[i] = dsf(p[i]); } void dsj(int i, int j) { p[dsf(i)] = dsf(j); } bool has(int i) { return !rem[i]; } void remove(int i) { if (i > 0 && rem[i-1]) dsj(i-1, i); if (i+1 < n && rem[i+1]) dsj(i, i+1); rem[i] = 1; } int next(int i) { return i == n ? n : !rem[i] ? i : dsf(i)+1; } }; int main() { ios::sync_with_stdio(false); cin.exceptions(cin.failbit); cin.tie(NULL); int k, n, m; cin >> n >> m >> k; int i1, j1, i2, j2; cin >> i1 >> j1 >> i2 >> j2, i1--, j1--, i2--, j2--; static char g[NM+1]; for (int i = 0; i < n; i++) { string s; cin >> s; for (int j = 0; j < m; j++) g[i*m+j] = s[j]; } vector<Range> row, col; for (int i = 0; i < n; i++) row.push_back(Range(m)); for (int i = 0; i < m; i++) col.push_back(Range(n)); static int d[NM]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) d[i*m+j] = -1; static bool fl[NM]; vector<pi> f; d[i1*m+j1] = 0, f.push_back({i1, j1}), row[i1].remove(j1), col[j1].remove(i1); for (int x = 0; ; x++) { for (int p = 0; p < int(f.size()); p++) { auto [i,j] = f[p]; fl[i*m+j] = true; if (i == i2 && j == j2) { cout << x << '\n'; return 0; } if (i > 0 && g[(i-1)*m+j] == '.' && d[(i-1)*m+j] == -1) d[(i-1)*m+j] = x, f.push_back({i-1,j}), row[i-1].remove(j), col[j].remove(i-1); if (i+1 < n && g[(i+1)*m+j] == '.' && d[(i+1)*m+j] == -1) d[(i+1)*m+j] = x, f.push_back({i+1,j}), row[i+1].remove(j), col[j].remove(i+1); if (j > 0 && g[i*m+j-1] == '.' && d[i*m+j-1] == -1) d[i*m+j-1] = x, f.push_back({i,j-1}), row[i].remove(j-1), col[j-1].remove(i); if (j+1 < m && g[i*m+j+1] == '.' && d[i*m+j+1] == -1) d[i*m+j+1] = x, f.push_back({i,j+1}), row[i].remove(j+1), col[j+1].remove(i); } vector<pi> half = f, g; for (auto [i,j] : f) { int p = row[i].next(max(0,j-k)); while (p < m && p <= j+k) { d[i*m+p] = x+1; if (abs(p-j) != k) { row[i].remove(p), col[p].remove(i); fl[i*m+p] = true; } half.push_back({i,p}), g.push_back({i,p}); p = row[i].next(p+1); } } for (auto [i,j] : half) if (row[i].has(j)) row[i].remove(j), col[j].remove(i); for (auto [i,j] : half) { int bound = k - (fl[i*m+j]?0:1); int p = col[j].next(max(0,i-bound)); while (p < n && p <= i+bound) { d[p*m+j] = x+1; g.push_back({p,j}); row[p].remove(j), col[j].remove(p); p = col[j].next(p+1); } } f = move(g); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...