Submission #1261576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261576		avighna	Obstacles for a Llama (IOI25_obstacles)	C++20	23 / 100	68 ms	8264 KiB

obstacles

#include <bits/stdc++.h>

std::vector<int> h, t;
int m;

bool b(int i, int j) {
  return t[i] > h[j];
}

int oned(int i, int j) {
  return i * m + j;
}

class UFDS {
public:
  std::vector<int> par;
  int n;
  UFDS() {}
  UFDS(int n) : n(n), par(n) {
    std::iota(par.begin(), par.end(), 0);
  }

  int root(int u) {
    return u == par[u] ? u : par[u] = root(par[u]);
  }

  void merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) {
      return;
    }
    par[v] = u;
  }
};

UFDS dsu;

void initialize(std::vector<int> T, std::vector<int> H) {
  h = H, t = T;
  m = h.size();
  const int n = t.size();
  dsu = UFDS(n * m);
  std::array<int, 4> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      for (int k = 0; k < 4; ++k) {
        int x = i + dx[k], y = j + dy[k];
        if (x < 0 or x >= n or y < 0 or y >= m) {
          continue;
        }
        if (b(i, j) and b(x, y)) {
          dsu.merge(oned(i, j), oned(x, y));
        }
      }
    }
  }
}

bool can_reach(int l, int r, int s, int d) {
  return dsu.root(oned(0, s)) == dsu.root(oned(0, d));
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17