Submission #373337

#	Time	Username	Problem	Language	Result	Execution time	Memory
373337		arujbansal	물병 (JOI14_bottle)	C++17	100 / 100	1996 ms	274140 KiB

bottle

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int long long

struct Edge {
    int u, v, w;

    Edge(int u, int v, int w) : u(u), v(v), w(w) {}

    bool operator<(const Edge &b) const {
        return w < b.w;
    }
};

const int MXN = 2100, INF = 1e15, MXP = 4e5 + 5, MXK = 20;
using pii = pair<int, int>;

int H, W, P, Q;
int grid[MXN][MXN], dist[MXN][MXN], bfs_par[MXN][MXN];

bool valid(int i, int j) {
    if (i < 1 || i > H || j < 1 || j > W) return false;
    if (grid[i][j] < 0) return false;

    return true;
}

int par[MXP], cost[MXP], tin[MXP], tout[MXP], binlift[MXK][MXP];
vector<int> g[MXP];
int new_node, timer;

int get(int x) {
    if (par[x] == x) return x;
    return par[x] = get(par[x]);
}

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

void unite(int x, int y, int w) {
    x = get(x), y = get(y);
    if (x == y) return;

    cost[new_node] = w;

    add_edge(x, new_node);
    add_edge(y, new_node);

    par[x] = new_node;
    par[y] = new_node;

    new_node++;
}

void dfs(int u, int p) {
    tin[u] = timer++;

    for (int k = 1; k < MXK; k++)
        binlift[k][u] = binlift[k - 1][binlift[k - 1][u]];

    for (const auto &v : g[u]) {
        if (v == p) continue;

        binlift[0][v] = u;

        dfs(v, u);
    }

    tout[u] = timer - 1;
}

bool is_anc(int v, int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}

int get_lca(int u, int v) {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;

    for (int i = MXK - 1; i >= 0; i--) {
        if (is_anc(binlift[i][u], v)) continue;
        u = binlift[i][u];
    }

    return binlift[0][u];
}

void solve() {
    cin >> H >> W >> P >> Q;

    for (int i = 0; i <= H + 2; i++) {
        for (int j = 0; j <= W + 2; j++) {
            grid[i][j] = -1;
            dist[i][j] = INF;
        }
    }

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            char x;
            cin >> x;

            if (x == '.') grid[i][j] = 0;
        }
    }

    deque<pii> dq;

    for (int i = 1; i <= P; i++) {
        int x, y;
        cin >> x >> y;

        grid[x][y] = i;

        dq.emplace_back(x, y);
        dist[x][y] = 0;
        bfs_par[x][y] = i;
    }

    int pos[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

    vector<Edge> edges;

    while (!dq.empty()) {
        auto cur = dq.front();
        dq.pop_front();

        int x = cur.first, y = cur.second;

        for (const auto &[dx, dy] : pos) {
            int nx = dx + x, ny = dy + y;

            if (!valid(nx, ny)) continue;

            if (dist[nx][ny] < INF) {
                if (bfs_par[x][y] == bfs_par[nx][ny]) continue;
                edges.emplace_back(bfs_par[x][y], bfs_par[nx][ny], dist[x][y] + dist[nx][ny]);
            } else {
                int wt = (grid[nx][ny] == 0);

                if (wt == 0) dq.emplace_front(nx, ny);
                else dq.emplace_back(nx, ny);

                dist[nx][ny] = dist[x][y] + wt;
                bfs_par[nx][ny] = bfs_par[x][y];
            }
        }
    }

    // for (int i = 1; i <= H; i++) {
    //     for (int j = 1; j <= W; j++) {
    //         cout << bfs_par[i][j] << " ";
    //     }

    //     cout << "\n";
    // }

    sort(all(edges));

    // for (const auto &[u, v, w] : edges) {
    //     cout << u << " " << v << " " << w << "\n";
    // }
    
    for (int i = 0; i < MXP; i++) {
        par[i] = i;
        cost[i] = INF;
    }

    new_node = P + 1;

    for (const auto &[u, v, w] : edges) {
        unite(u, v, w);
    }

    for (int i = 1; i < new_node; i++) {
        if (get(i) == i) add_edge(i, 0);
    }

    dfs(0, -1);

    // for (int i = 0; i < MXP; i++) {
    //     for (const auto &v : g[i]) {
    //         cout << i << " " << v << "\n";
    //     }
    // }

    // dbg(get_lca(1, 2));

    while (Q--) {
        int u, v;
        cin >> u >> v;

        int lca = get_lca(u, v);
        int ans = cost[lca];

        cout << (ans < INF ? ans : -1) << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30