Submission #838662

#	Time	Username	Problem	Language	Result	Execution time	Memory
838662		makrav	Maze (JOI23_ho_t3)	C++14	51 / 100	2073 ms	207172 KiB

Main

#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;
    }

    pair<int, int> getkth(int v, int tl, int tr, int l, int r, int k) {
        if (tr <= l || tl >= r) return { -1, 0 };
        if (l <= tl && tr <= r) {
            if (t[v].sm < k) return { -1, t[v].sm };
            if (tl + 1 == tr) return { tl, t[v].sm };
            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;
        pii lft = getkth(v * 2, tl, tm, l, r, k);
        if (lft.ff != -1) return lft;
        else return getkth(v * 2 + 1, tm, tr, l, r, k - lft.sc);
    }
};

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];
        if (k == 1) {
            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);
                        }
                    }
                }
            }
        }
        else {
            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).ff;
                while (nw != -1) {
                    if (!check({ i, j }, { row, nw }, k) && a[row][nw] == '#') {
                        K++;
                        nw = sg[row].getkth(1, 0, m, l, r, K).ff;
                        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).ff;
                }
            }
        }
    }
    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();
      |              ^

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