oj.uz

Submission #156078

# Submission time Handle Problem Language Result Execution time Memory
156078 2019-10-03T07:57:39 Z atoiz 물병 (JOI14_bottle) C++14
100 / 100
 1812 ms 361884 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 * 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 * 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 195460 KB Output is correct
2 Correct 241 ms 196652 KB Output is correct
3 Correct 241 ms 197272 KB Output is correct
4 Correct 292 ms 197884 KB Output is correct
5 Correct 307 ms 198008 KB Output is correct
6 Correct 322 ms 197524 KB Output is correct
7 Correct 312 ms 199160 KB Output is correct
8 Correct 309 ms 199596 KB Output is correct
9 Correct 274 ms 199296 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 215800 KB Output is correct
2 Correct 243 ms 205524 KB Output is correct
3 Correct 614 ms 271028 KB Output is correct
4 Correct 830 ms 292280 KB Output is correct
5 Correct 962 ms 312428 KB Output is correct
6 Correct 600 ms 270632 KB Output is correct
7 Correct 904 ms 292584 KB Output is correct
8 Correct 1177 ms 312244 KB Output is correct
9 Correct 1309 ms 354976 KB Output is correct
10 Correct 699 ms 291636 KB Output is correct
11 Correct 779 ms 291080 KB Output is correct
12 Correct 448 ms 274160 KB Output is correct
13 Correct 496 ms 267064 KB Output is correct
14 Correct 457 ms 274412 KB Output is correct
15 Correct 495 ms 267220 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 215704 KB Output is correct
2 Correct 241 ms 204504 KB Output is correct
3 Correct 563 ms 267500 KB Output is correct
4 Correct 864 ms 292372 KB Output is correct
5 Correct 999 ms 312412 KB Output is correct
6 Correct 1192 ms 354908 KB Output is correct
7 Correct 720 ms 295172 KB Output is correct
8 Correct 985 ms 295760 KB Output is correct
9 Correct 450 ms 277156 KB Output is correct
10 Correct 523 ms 271248 KB Output is correct
11 Correct 479 ms 261248 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 273124 KB Output is correct
2 Correct 1572 ms 317156 KB Output is correct
3 Correct 859 ms 292164 KB Output is correct
4 Correct 1756 ms 337444 KB Output is correct
5 Correct 1812 ms 359112 KB Output is correct
6 Correct 1189 ms 302596 KB Output is correct
7 Correct 775 ms 295204 KB Output is correct
8 Correct 474 ms 282296 KB Output is correct
9 Correct 1479 ms 361800 KB Output is correct
10 Correct 1339 ms 313904 KB Output is correct
11 Correct 1450 ms 361884 KB Output is correct
12 Correct 1311 ms 344452 KB Output is correct