제출 #1067101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067101		juicy	물병 (JOI14_bottle)	C++17	100 / 100	890 ms	116564 KiB

bottle

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e3 + 5, MAX = 2e5 + 5;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int n, m, p, q;
int lab[N][N], d[N][N], res[MAX], s[MAX], t[MAX], pr[MAX];
char a[N][N];
vector<int> queries[MAX], ver[MAX];

bool inside(int i, int j) {
  return 0 < i && i <= n && 0 < j && j <= m && a[i][j] != '#';
}

void mrg(int u, int v, int w) {
  if ((u = pr[u]) != (v = pr[v])) {
    if (ver[u].size() < ver[v].size()) {
      swap(u, v);
    }
    for (int x : ver[v]) {
      pr[x] = u;
      ver[u].push_back(x);
    }
    for (auto id : queries[v]) {
      if (pr[s[id]] == pr[t[id]] && res[id] == -1) {
        res[id] += w;
      } else {
        queries[u].push_back(id);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> p >> q;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> a[i][j];
    }
  }
  queue<array<int, 2>> que;
  for (int i = 1; i <= p; ++i) {
    int r, c; cin >> r >> c;
    lab[r][c] = i;
    que.push({r, c});
  }
  while (que.size()) {
    auto [x, y] = que.front(); que.pop();
    for (int dr = 0; dr < 4; ++dr) {
      int i = x + dx[dr], j = y + dy[dr];
      if (inside(i, j) && !lab[i][j]) {
        lab[i][j] = lab[x][y];
        d[i][j] = d[x][y] + 1;
        que.push({i, j});
      }
    }
  }
  vector<array<int, 3>> edges;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (lab[i][j]) {
        for (int dr = 0; dr < 4; ++dr) {
          int x = i + dx[dr], y = j + dy[dr];
          if (inside(x, y) && lab[x][y] != lab[i][j]) {
            edges.push_back({d[x][y] + d[i][j] + 1, lab[i][j], lab[x][y]});
          }
        }
      }
    }
  }
  for (int i = 1; i <= p; ++i) {
    ver[i].push_back(i);
    pr[i] = i; 
  }
  for (int i = 1; i <= q; ++i) {
    cin >> s[i] >> t[i];
    res[i] = -1;
    queries[s[i]].push_back(i);
    queries[t[i]].push_back(i);
  }
  sort(edges.begin(), edges.end());
  for (auto [w, u, v] : edges) {
    mrg(u, v, w);
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

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