oj.uz

Submission #1067101

# Submission time Handle Problem Language Result Execution time Memory
1067101 2024-08-20T11:23:44 Z juicy 물병 (JOI14_bottle) C++17
100 / 100
 890 ms 116564 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10588 KB Output is correct
2 Correct 6 ms 11976 KB Output is correct
3 Correct 8 ms 12180 KB Output is correct
4 Correct 41 ms 22584 KB Output is correct
5 Correct 46 ms 22716 KB Output is correct
6 Correct 41 ms 22200 KB Output is correct
7 Correct 40 ms 22208 KB Output is correct
8 Correct 41 ms 22840 KB Output is correct
9 Correct 41 ms 23540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 32048 KB Output is correct
2 Correct 33 ms 15512 KB Output is correct
3 Correct 216 ms 50064 KB Output is correct
4 Correct 261 ms 52676 KB Output is correct
5 Correct 301 ms 56188 KB Output is correct
6 Correct 205 ms 50064 KB Output is correct
7 Correct 259 ms 52752 KB Output is correct
8 Correct 300 ms 56256 KB Output is correct
9 Correct 305 ms 62648 KB Output is correct
10 Correct 236 ms 50896 KB Output is correct
11 Correct 240 ms 52484 KB Output is correct
12 Correct 128 ms 45576 KB Output is correct
13 Correct 138 ms 43136 KB Output is correct
14 Correct 132 ms 45572 KB Output is correct
15 Correct 133 ms 43212 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32028 KB Output is correct
2 Correct 33 ms 14408 KB Output is correct
3 Correct 183 ms 49748 KB Output is correct
4 Correct 260 ms 52740 KB Output is correct
5 Correct 304 ms 56268 KB Output is correct
6 Correct 305 ms 62840 KB Output is correct
7 Correct 224 ms 50964 KB Output is correct
8 Correct 256 ms 52940 KB Output is correct
9 Correct 130 ms 45932 KB Output is correct
10 Correct 132 ms 43768 KB Output is correct
11 Correct 136 ms 42740 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 63488 KB Output is correct
2 Correct 550 ms 91256 KB Output is correct
3 Correct 239 ms 50952 KB Output is correct
4 Correct 697 ms 99764 KB Output is correct
5 Correct 890 ms 111148 KB Output is correct
6 Correct 370 ms 71020 KB Output is correct
7 Correct 234 ms 51020 KB Output is correct
8 Correct 96 ms 43204 KB Output is correct
9 Correct 865 ms 116564 KB Output is correct
10 Correct 471 ms 88388 KB Output is correct
11 Correct 726 ms 109692 KB Output is correct
12 Correct 552 ms 99496 KB Output is correct