oj.uz

Submission #373337

# Submission time Handle Problem Language Result Execution time Memory
373337 2021-03-04T07:23:52 Z arujbansal 물병 (JOI14_bottle) C++17
100 / 100
 1996 ms 274140 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17516 KB Output is correct
2 Correct 15 ms 19404 KB Output is correct
3 Correct 16 ms 19908 KB Output is correct
4 Correct 96 ms 21868 KB Output is correct
5 Correct 119 ms 21944 KB Output is correct
6 Correct 97 ms 21868 KB Output is correct
7 Correct 98 ms 21868 KB Output is correct
8 Correct 129 ms 22328 KB Output is correct
9 Correct 99 ms 21868 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 46392 KB Output is correct
2 Correct 78 ms 30516 KB Output is correct
3 Correct 571 ms 122016 KB Output is correct
4 Correct 683 ms 126928 KB Output is correct
5 Correct 719 ms 132096 KB Output is correct
6 Correct 563 ms 122016 KB Output is correct
7 Correct 670 ms 127256 KB Output is correct
8 Correct 720 ms 132144 KB Output is correct
9 Correct 788 ms 139904 KB Output is correct
10 Correct 609 ms 121396 KB Output is correct
11 Correct 640 ms 123796 KB Output is correct
12 Correct 285 ms 115800 KB Output is correct
13 Correct 421 ms 111128 KB Output is correct
14 Correct 265 ms 115856 KB Output is correct
15 Correct 428 ms 111124 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 46360 KB Output is correct
2 Correct 63 ms 27940 KB Output is correct
3 Correct 460 ms 119748 KB Output is correct
4 Correct 693 ms 126864 KB Output is correct
5 Correct 721 ms 132272 KB Output is correct
6 Correct 787 ms 140124 KB Output is correct
7 Correct 615 ms 121244 KB Output is correct
8 Correct 669 ms 127064 KB Output is correct
9 Correct 278 ms 115944 KB Output is correct
10 Correct 423 ms 111252 KB Output is correct
11 Correct 378 ms 109424 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 126880 KB Output is correct
2 Correct 1632 ms 223080 KB Output is correct
3 Correct 625 ms 121400 KB Output is correct
4 Correct 1822 ms 242632 KB Output is correct
5 Correct 1996 ms 263928 KB Output is correct
6 Correct 880 ms 141312 KB Output is correct
7 Correct 603 ms 121244 KB Output is correct
8 Correct 208 ms 110112 KB Output is correct
9 Correct 1738 ms 274140 KB Output is correct
10 Correct 1449 ms 207120 KB Output is correct
11 Correct 1746 ms 254424 KB Output is correct
12 Correct 1594 ms 230464 KB Output is correct