oj.uz

Submission #156077

# Submission time Handle Problem Language Result Execution time Memory
156077 2019-10-03T07:55:45 Z atoiz 물병 (JOI14_bottle) C++14
0 / 100
 1793 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);
    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 9 ms 6392 KB Output is correct
2 Correct 11 ms 7672 KB Output is correct
3 Correct 15 ms 8208 KB Output is correct
4 Correct 90 ms 8696 KB Output is correct
5 Correct 88 ms 8924 KB Output is correct
6 Correct 88 ms 8496 KB Output is correct
7 Runtime error 529 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 46 ms 26744 KB Output is correct
2 Correct 53 ms 16432 KB Output is correct
3 Correct 468 ms 82112 KB Output is correct
4 Correct 681 ms 103256 KB Output is correct
5 Correct 817 ms 123336 KB Output is correct
6 Correct 460 ms 81804 KB Output is correct
7 Correct 720 ms 103504 KB Output is correct
8 Correct 794 ms 123216 KB Output is correct
9 Correct 979 ms 165980 KB Output is correct
10 Runtime error 894 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 48 ms 26716 KB Output is correct
2 Correct 49 ms 15520 KB Output is correct
3 Correct 356 ms 78616 KB Output is correct
4 Correct 688 ms 103392 KB Output is correct
5 Correct 811 ms 123432 KB Output is correct
6 Correct 1044 ms 166236 KB Output is correct
7 Runtime error 1057 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 642 ms 84084 KB Output is correct
2 Correct 1118 ms 128324 KB Output is correct
3 Correct 565 ms 103152 KB Output is correct
4 Correct 1793 ms 148496 KB Output is correct
5 Correct 1532 ms 170016 KB Output is correct
6 Runtime error 1183 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -