oj.uz

Submission #909628

# Submission time Handle Problem Language Result Execution time Memory
909628 2024-01-17T09:58:52 Z MilosMilutinovic 물병 (JOI14_bottle) C++14
100 / 100
 2488 ms 288704 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1156 KB Output is correct
2 Correct 5 ms 1184 KB Output is correct
3 Correct 7 ms 1948 KB Output is correct
4 Correct 82 ms 3848 KB Output is correct
5 Correct 93 ms 3848 KB Output is correct
6 Correct 79 ms 3592 KB Output is correct
7 Correct 73 ms 3596 KB Output is correct
8 Correct 97 ms 4260 KB Output is correct
9 Correct 86 ms 3836 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11520 KB Output is correct
2 Correct 82 ms 19768 KB Output is correct
3 Correct 667 ms 112956 KB Output is correct
4 Correct 1093 ms 177368 KB Output is correct
5 Correct 1399 ms 177228 KB Output is correct
6 Correct 707 ms 114980 KB Output is correct
7 Correct 1077 ms 177008 KB Output is correct
8 Correct 1411 ms 177492 KB Output is correct
9 Correct 2112 ms 288704 KB Output is correct
10 Correct 942 ms 176668 KB Output is correct
11 Correct 1016 ms 176612 KB Output is correct
12 Correct 375 ms 142612 KB Output is correct
13 Correct 498 ms 141272 KB Output is correct
14 Correct 365 ms 142600 KB Output is correct
15 Correct 500 ms 141976 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 11524 KB Output is correct
2 Correct 82 ms 19696 KB Output is correct
3 Correct 480 ms 112884 KB Output is correct
4 Correct 1073 ms 179284 KB Output is correct
5 Correct 1482 ms 175520 KB Output is correct
6 Correct 2146 ms 287972 KB Output is correct
7 Correct 966 ms 175768 KB Output is correct
8 Correct 1100 ms 178276 KB Output is correct
9 Correct 391 ms 142956 KB Output is correct
10 Correct 480 ms 143052 KB Output is correct
11 Correct 430 ms 97356 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 115008 KB Output is correct
2 Correct 1826 ms 186124 KB Output is correct
3 Correct 896 ms 177128 KB Output is correct
4 Correct 2153 ms 213804 KB Output is correct
5 Correct 2488 ms 243336 KB Output is correct
6 Correct 1270 ms 182196 KB Output is correct
7 Correct 896 ms 176196 KB Output is correct
8 Correct 319 ms 142396 KB Output is correct
9 Correct 2210 ms 240824 KB Output is correct
10 Correct 1842 ms 177088 KB Output is correct
11 Correct 2466 ms 248380 KB Output is correct
12 Correct 2251 ms 224276 KB Output is correct