제출 #909628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
909628		MilosMilutinovic	물병 (JOI14_bottle)	C++14	100 / 100	2488 ms	288704 KiB

bottle

#include <bits/stdc++.h>

using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k, q;
  cin >> n >> m >> k >> q;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  vector<int> x(k);
  vector<int> y(k);
  for (int i = 0; i < k; i++) {
    cin >> x[i] >> y[i];
    --x[i]; --y[i];
  }
  vector<vector<int>> idx(n, vector<int>(m, -1));
  vector<vector<int>> dist(n, vector<int>(m, 0));
  vector<array<int, 4>> que;
  for (int i = 0; i < k; i++) {
    idx[x[i]][y[i]] = i;
    dist[x[i]][y[i]] = 0;
    que.push_back({x[i], y[i], 0, i});
  }
  auto Valid = [&](int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m && s[x][y] != '#';
  };
  vector<vector<pair<int, int>>> g(k);
  vector<int> par(k);
  iota(par.begin(), par.end(), 0);
  function<int(int)> GetPar = [&](int x) {
    return par[x] == x ? x : par[x] = GetPar(par[x]);
  };
  auto Unite = [&](int x, int y, int w) {
    if (GetPar(x) == GetPar(y)) {
      return;
    }
    par[GetPar(x)] = GetPar(y);
    g[x].push_back({y, w});
    g[y].push_back({x, w});
  };
  vector<array<int, 3>> edges;
  for (int b = 0; b < (int) que.size(); b++) {
    int x = que[b][0];
    int y = que[b][1];
    int d = que[b][2];
    int i = que[b][3];
    for (int dir = 0; dir < 4; dir++) {
      int nx = x + dx[dir];
      int ny = y + dy[dir];
      if (!Valid(nx, ny)) {
        continue;
      }
      if (idx[nx][ny] != -1) {
        edges.push_back({d + dist[nx][ny], i, idx[nx][ny]});
      } else {
        idx[nx][ny] = i;
        dist[nx][ny] = d + 1;
        que.push_back({nx, ny, d + 1, i});
      }
    }
  }
  sort(edges.begin(), edges.end());
  for (auto& p : edges) {
    Unite(p[1], p[2], p[0]);
  }
  const int L = 20;
  vector<vector<int>> jump(k, vector<int>(L));
  vector<vector<int>> up(k, vector<int>(L));
  vector<int> dep(k, -1);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    jump[v][0] = pv;
    for (int i = 1; i < L; i++) {
      jump[v][i] = jump[jump[v][i - 1]][i - 1];
    }
    dep[v] = dep[pv] + 1;
    for (auto& p : g[v]) { 
      int to = p.first;
      int w = p.second;
      if (to == pv) {
        continue;
      }
      up[to][0] = w;
      Dfs(to, v);
    }
  };
  for (int i = 0; i < k; i++) {
    if (GetPar(i) == i) {
      Dfs(i, i);
    }
  }
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < k; i++) {
      up[i][j] = max(up[i][j - 1], up[jump[i][j - 1]][j - 1]);
    }
  }
  auto LCA = [&](int x, int y) {
    if (dep[x] > dep[y]) {
      swap(x, y);    
    }
    for (int i = L - 1; i >= 0; i--) {
      if (dep[jump[y][i]] >= dep[x]) {
        y = jump[y][i];
      }
    }
    for (int i = L - 1; i >= 0; i--) {
      if (jump[x][i] != jump[y][i]) {
        x = jump[x][i];
        y = jump[y][i];
      }
    }
    return x == y ? x : jump[x][0];
  };
  auto Query = [&](int x, int y) {
    int d = dep[x] - dep[y];
    int mx = 0;
    for (int i = L - 1; i >= 0; i--) {
      if (d >> i & 1) {
        mx = max(mx, up[x][i]);
        x = jump[x][i];
      }
    }
    return mx;
  };
  while (q--) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    if (GetPar(a) != GetPar(b)) {
      cout << -1 << '\n';
      continue;
    }
    int c = LCA(a, b);
    cout << max(Query(a, c), Query(b, c)) << '\n';
  }
  return 0;
}

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