Submission #1262261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262261		avighna	장애물 (IOI25_obstacles)	C++20	0 / 100	48 ms	4936 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) {
  {
    std::vector<int> h_new;
    int cur = H[0];
    h_new.push_back(cur);
    for (int i = 1; i < H.size(); ++i) {
      if (H[i] <= cur) {
        continue;
      }
      cur = H[i];
      h_new.push_back(cur);
    }
    H = h_new;
  }
  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: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17