oj.uz

Submission #156071

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

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;

void add_edge(int u, int v, int w)
{
    if (same(u, v)) return;
    join(u, v);
    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];
    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];
    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 10 ms 6008 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 46 ms 24440 KB Output is correct
2 Correct 46 ms 12024 KB Output is correct
3 Correct 339 ms 57412 KB Output is correct
4 Correct 564 ms 63208 KB Output is correct
5 Correct 607 ms 71160 KB Output is correct
6 Correct 396 ms 61236 KB Output is correct
7 Correct 557 ms 67376 KB Output is correct
8 Correct 643 ms 70908 KB Output is correct
9 Correct 718 ms 76880 KB Output is correct
10 Correct 399 ms 66168 KB Output is correct
11 Correct 486 ms 66552 KB Output is correct
12 Correct 154 ms 56184 KB Output is correct
13 Correct 249 ms 56532 KB Output is correct
14 Correct 156 ms 56360 KB Output is correct
15 Correct 244 ms 56396 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 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 567 ms 59156 KB Output isn't correct
2 Halted 0 ms 0 KB -