oj.uz

Submission #156074

# Submission time Handle Problem Language Result Execution time Memory
156074 2019-10-03T07:47:46 Z atoiz 물병 (JOI14_bottle) C++14
30 / 100
 872 ms 72968 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>

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];
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]) add_edge(col[x0][y0], col[x][y], dis[x0][y0] + dis[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 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 Incorrect 11 ms 6136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 24440 KB Output is correct
2 Correct 52 ms 12024 KB Output is correct
3 Correct 397 ms 57436 KB Output is correct
4 Correct 563 ms 63300 KB Output is correct
5 Correct 872 ms 67128 KB Output is correct
6 Correct 367 ms 57340 KB Output is correct
7 Correct 670 ms 63288 KB Output is correct
8 Correct 660 ms 67124 KB Output is correct
9 Correct 805 ms 72968 KB Output is correct
10 Correct 388 ms 62456 KB Output is correct
11 Correct 537 ms 62580 KB Output is correct
12 Correct 156 ms 52216 KB Output is correct
13 Correct 247 ms 52472 KB Output is correct
14 Correct 147 ms 52324 KB Output is correct
15 Correct 244 ms 52472 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 24440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 568 ms 59116 KB Output isn't correct
2 Halted 0 ms 0 KB -