oj.uz

Submission #156076

# Submission time Handle Problem Language Result Execution time Memory
156076 2019-10-03T07:54:54 Z atoiz 물병 (JOI14_bottle) C++14
0 / 100
 1743 ms 524292 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <tuple>

using namespace std;

const int MAXN = 200007, MAXH = 2007, LOG = 18;
const int DX[4] = {-1, 1, 0, 0}, DY[4] = {0, 0, -1, 1};
vector<pair<int, int>> gr[MAXN], edges[MAXH << 2];
int h, w, p, q;
int col[MAXH][MAXH], dis[MAXH][MAXH];
int anc[LOG][MAXN], up[LOG][MAXN], dep[MAXN];
string str[MAXH];
int a[MAXN], b[MAXN];

int dsu[MAXN], sz[MAXN];
void init(int n) { for (int i = 0; i < n; ++i) dsu[i] = i, sz[i] = 1; }
int get(int i) { return (i == dsu[i] ? i : dsu[i] = get(dsu[i])); }
bool same(int i, int j) { return get(i) == get(j); }
void join(int i, int j) { i = get(i), j = get(j); if (i == j) return; if (sz[i] < sz[j]) swap(i, j); sz[i] += sz[j], dsu[j] = i; }

bool is_valid(int i, int j) { return i >= 0 && i < h && j >= 0 && j < w && str[i][j] != '#'; }

int qu_x[MAXH * MAXH], qu_y[MAXH * MAXH], fr, rr, last = -1;

void add_edge(int u, int v, int _w)
{
    if (same(u, v)) return;
    join(u, v);
    assert(_w >= last - 1); last = _w;
    gr[u].emplace_back(_w, v);
    gr[v].emplace_back(_w, u);
}

void dfs(int u)
{
    for (auto a : gr[u]) if (a.second != anc[0][u]) {
        dep[a.second] = dep[u] + 1;
        anc[0][a.second] = u;
        up[0][a.second] = a.first;
        dfs(a.second);
    }
}

int max_path(int u, int v)
{
    if (!same(u, v)) return -1;
    int ans = 0;
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LOG - 1; i >= 0; --i) if (dep[u] - (1 << i) >= dep[v]) ans = max(ans, up[i][u]), u = anc[i][u];
    assert(dep[u] == dep[v]);
    if (u == v) return ans;
    for (int i = LOG - 1; i >= 0; --i) if (anc[i][u] != anc[i][v]) ans = max(ans, max(up[i][u], up[i][v])), u = anc[i][u], v = anc[i][v];
    assert(anc[0][u] == anc[0][v]);
    return max(ans, max(up[0][u], up[0][v]));
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> h >> w >> p >> q;
    for (int i = 0; i < h; ++i) cin >> str[i];
    for (int i = 1; i <= p; ++i) {
        cin >> a[i] >> b[i];
        col[--a[i]][--b[i]] = i;
        qu_x[rr] = a[i], qu_y[rr] = b[i]; ++rr;
    }

    init(p + 1);
    while (fr < rr) {
        int x = qu_x[fr], y = qu_y[fr]; ++fr;
        for (int d = 0; d < 4; ++d) {
            int x0 = x + DX[d], y0 = y + DY[d];
            if (!is_valid(x0, y0)) continue;
            if (col[x0][y0]) edges[dis[x0][y0] + dis[x][y]].emplace_back(col[x0][y0], col[x][y]);
            else {
                col[x0][y0] = col[x][y];
                dis[x0][y0] = dis[x][y] + 1;
                qu_x[rr] = x0, qu_y[rr] = y0; ++rr;
            }
        }
    }

    for (int i = 0; i < (MAXH << 2); ++i) for (auto a : edges[i]) add_edge(a.first, a.second, i);

    for (int u = 1; u <= p; ++u) if (!anc[0][u]) dfs(u);
    for (int lg = 1; lg < LOG; ++lg) for (int u = 1; u <= p; ++u) {
        up[lg][u] = max(up[lg - 1][u], up[lg - 1][anc[lg - 1][u]]);
        anc[lg][u] = anc[lg - 1][anc[lg - 1][u]];
    }

    for (int i = 0; i < q; ++i) {
        int u, v;
        cin >> u >> v;
        cout << max_path(u, v) << '\n';
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6392 KB Output is correct
2 Correct 12 ms 7672 KB Output is correct
3 Correct 14 ms 8288 KB Output is correct
4 Correct 90 ms 10232 KB Output is correct
5 Correct 93 ms 10340 KB Output is correct
6 Correct 90 ms 9936 KB Output is correct
7 Runtime error 516 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 26744 KB Output is correct
2 Correct 59 ms 16560 KB Output is correct
3 Correct 477 ms 81948 KB Output is correct
4 Correct 701 ms 103180 KB Output is correct
5 Correct 810 ms 123148 KB Output is correct
6 Correct 619 ms 81856 KB Output is correct
7 Correct 692 ms 103500 KB Output is correct
8 Correct 799 ms 123216 KB Output is correct
9 Correct 987 ms 165832 KB Output is correct
10 Runtime error 926 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26776 KB Output is correct
2 Correct 51 ms 15920 KB Output is correct
3 Correct 355 ms 82492 KB Output is correct
4 Correct 690 ms 107276 KB Output is correct
5 Correct 904 ms 127636 KB Output is correct
6 Correct 1020 ms 169912 KB Output is correct
7 Runtime error 1161 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 83948 KB Output is correct
2 Correct 1103 ms 136288 KB Output is correct
3 Correct 537 ms 107184 KB Output is correct
4 Correct 1631 ms 156492 KB Output is correct
5 Correct 1743 ms 178352 KB Output is correct
6 Runtime error 1257 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -