oj.uz

Submission #838629

# Submission time Handle Problem Language Result Execution time Memory
838629 2023-08-27T13:32:38 Z makrav Maze (JOI23_ho_t3) C++14
0 / 100
 1 ms 468 KB 
#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 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

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -