Submission #838645

#TimeUsernameProblemLanguageResultExecution timeMemory
838645makravMaze (JOI23_ho_t3)C++14
8 / 100
394 ms208664 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vei; typedef vector<vei> vevei; #define all(a) (a).begin(), (a).end() #define sz(a) (int) a.size() #define con cout << "NO\n" #define coe cout << "YES\n"; #define str string #define pb push_back #define ff first #define sc second #define pii pair<int, int> #define mxe max_element #define mne min_element #define stf shrink_to_fit #define f(i, l, r) for (int i = (l); i < (r); i++) #define double ld vector<str> a; vector<vector<pii>> comps; vector<vector<int>> used; int n, m; void dfs(int i, int j) { used[i][j] = 1; comps.back().pb({ i, j }); if (i - 1 >= 0 && a[i - 1][j] == '.' && !used[i - 1][j]) dfs(i - 1, j); if (i + 1 < n && a[i + 1][j] == '.' && !used[i + 1][j]) dfs(i + 1, j); if (j - 1 >= 0 && a[i][j - 1] == '.' && !used[i][j - 1]) dfs(i, j - 1); if (j + 1 < m && a[i][j + 1] == '.' && !used[i][j + 1]) dfs(i, j + 1); } struct node { int sm; node() = default; node(int a) { sm = a; } }; struct segtree { int n; vector<int> a; vector<node> t; segtree() = default; segtree(int n_, vector<int> a_) { n = n_; a = a_; t.resize(4 * n); build(1, 0, n); } void build(int v, int tl, int tr) { if (tl + 1 == tr) { t[v] = node(a[tl]); return; } int tm = (tl + tr) / 2; build(v * 2, tl, tm); build(v * 2 + 1, tm, tr); t[v].sm = t[v * 2].sm + t[v * 2 + 1].sm; } void upd(int v, int tl, int tr, int pos, int val) { if (tl + 1 == tr) { t[v] = node(val);return; } int tm = (tl + tr) / 2; if (pos < tm) { upd(v * 2, tl, tm, pos, val); } else { upd(v * 2 + 1, tm, tr, pos, val); } t[v].sm = t[v * 2].sm + t[v * 2 + 1].sm; } int getkth(int v, int tl, int tr, int l, int r, int k) { if (tr <= l || tl >= r) return -1; if (l <= tl && tr <= r) { if (t[v].sm < k) return -1; if (tl + 1 == tr) return tl; int tm = (tl + tr) / 2; if (t[v * 2].sm >= k) return getkth(v * 2, tl, tm, l, r, k); else return getkth(v * 2 + 1, tm, tr, l, r, k - t[v * 2].sm); } int tm = (tl + tr) / 2; int lft = getkth(v * 2, tl, tm, l, r, k); if (lft != -1) return lft; else return getkth(v * 2 + 1, tm, tr, l, r, k); } }; bool check(pii a, pii b, int k) { return (max(abs(a.ff - b.ff), abs(a.sc - b.sc)) <= k && min(abs(a.ff - b.ff), abs(a.sc - b.sc)) <= k - 1); } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int k; cin >> n >> m >> k; pii s, g; cin >> s.ff >> s.sc >> g.ff >> g.sc; s.ff--; s.sc--; g.ff--; g.sc--; a.resize(n); used.assign(n, vector<int>(m, 0)); f(i, 0, n) cin >> a[i]; vector<vector<int>> comp(n, vector<int>(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == '.' && used[i][j] == 0) { comps.pb({}); dfs(i, j); for (auto& u : comps.back()) { comp[u.ff][u.sc] = sz(comps) - 1; } } } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == '#') { comps.pb({ {i, j} }); comp[i][j] = sz(comps) - 1; } } } vector<vector<int>> dist(n, vector<int>(m, -1)); vector<segtree> sg(n); vector<int> B(m, 1); f(i, 0, n) { sg[i] = segtree(m, B); } queue<pair<int, int>> q; for (auto& u : comps[comp[s.ff][s.sc]]) { q.push(u); dist[u.ff][u.sc] = 0; sg[u.ff].upd(1, 0, m, u.sc, 0); } while (!q.empty()) { auto [i, j] = q.front(); q.pop(); int curd = dist[i][j]; for (int i1 = i - 2; i1 <= i + 2; i1++) { for (int j1 = j - (2 - abs(i - i1)); j1 <= j + abs(2 - abs(i - i1)); j1++) { if (0 <= i1 && i1 < n && 0 <= j1 && j1 < m) { if ((!check({ i, j }, { i1, j1 }, k) && a[i1][j1] == '#') || dist[i1][j1] != -1) continue; for (auto& u : comps[comp[i1][j1]]) { dist[u.ff][u.sc] = curd + 1; q.push(u); } } } } // for (int row = max(0, i - k - 1); row <= min(n - 1, i + k + 1); row++) { // int l = max(0, j - k - 1), r = min(m - 1, j + k + 1) + 1; // if (row == i - k - 1 || row == i + k + 1) { // l = max(0, j - k + 1); // r = min(m - 1, j + k - 1) + 1; // } // if (row == i - k || row == i + k) { // l = max(0, j - k); // r = min(m - 1, j + k) + 1; // } // int K = 1; // int nw = sg[row].getkth(1, 0, m, l, r, K); // while (nw != -1) { // if (!check({ i, j }, { row, nw }, k) && a[row][nw] == '#') { // K++; // nw = sg[row].getkth(1, 0, m, l, r, K); // continue; // } // for (auto& u : comps[comp[row][nw]]) { // dist[u.ff][u.sc] = curd + 1; // q.push(u); // sg[u.ff].upd(1, 0, m, u.sc, 0); // } // nw = sg[row].getkth(1, 0, m, l, r, K); // } // } } cout << dist[g.ff][g.sc] << '\n'; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:155:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |         auto [i, j] = q.front();
      |              ^
#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...