oj.uz

Submission #521266

# Submission time Handle Problem Language Result Execution time Memory
521266 2022-02-01T11:13:47 Z KoD Teoretičar (COCI18_teoreticar) C++17
130 / 130
 3824 ms 103924 KB 
#include <bits/stdc++.h>
#define ENABLE_AVX2

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

class Range {
  struct Iter {
    int itr;
    constexpr Iter(const int pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { ++itr; }
    constexpr bool operator!=(const Iter &other) const noexcept {
      return itr != other.itr;
    }
    constexpr int operator*() const noexcept { return itr; }
  };
  const Iter first, last;

public:
  explicit constexpr Range(const int first, const int last) noexcept
      : first(first), last(std::max(first, last)) {}
  constexpr Iter begin() const noexcept { return first; }
  constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }

class UnionFind {
  int components;
  std::vector<int> data;

public:
  explicit UnionFind(const int size = 0)
      : components(size), data(size, (int)-1) {}

  int size() const { return data.size(); }
  int count() const { return components; }

  int leader(const int u) {
    assert(0 <= u and u < size());
    return data[u] < 0 ? u : data[u] = leader(data[u]);
  }

  int size(const int u) {
    assert(0 <= u and u < size());
    return -data[leader(u)];
  }

  std::pair<int, bool> merge(int u, int v) {
    assert(0 <= u and u < size());
    assert(0 <= v and v < size());
    u = leader(u);
    v = leader(v);
    if (u == v)
      return std::make_pair(u, false);
    if (data[u] > data[v])
      std::swap(u, v);
    components -= 1;
    data[u] += data[v];
    data[v] = u;
    return std::make_pair(u, true);
  }

  bool same(const int u, const int v) {
    assert(0 <= u and u < size());
    assert(0 <= v and v < size());
    return leader(u) == leader(v);
  }

  std::vector<std::vector<int>> decompose() {
    std::vector<int> buf(size()), len(size());
    for (const int i : rep(size()))
      len[buf[i] = leader(i)]++;
    std::vector<std::vector<int>> ret(size());
    for (const int i : rep(size()))
      ret[i].reserve(len[i]);
    for (const int i : rep(size()))
      ret[buf[i]].push_back(i);
    ret.erase(
        std::remove_if(ret.begin(), ret.end(),
                       [&](const std::vector<int> &v) { return v.empty(); }),
        ret.end());
    return ret;
  }
};

#ifdef ENABLE_AVX2
#define TARGET_AVX2 __attribute__((target("avx2")))
#else
#define TARGET_AVX2
#endif

TARGET_AVX2 constexpr int countl_zero(u64 x) {
#ifdef __GNUC__
  return x == 0 ? 64 : __builtin_clzll(x);
#else
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x |= x >> 32;
  return 64 - countr_zero(~x);
#endif
}

TARGET_AVX2 constexpr int bit_width(const u64 x) { return 64 - countl_zero(x); }

TARGET_AVX2 constexpr int ceil_log2(const u64 x) {
#ifdef __GNUC__
  return x == 0 ? 0 : bit_width(x - 1);
#else
  int e = 0;
  while (((u64)1 << e) < x)
    ++e;
  return e;
#endif
}

template <class T> bool setmax(T &lhs, const T &rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

template <class F> struct RecursiveLambda : private F {
  explicit constexpr RecursiveLambda(F &&f) : F(std::forward<F>(f)) {}
  template <class... Args>
  constexpr decltype(auto) operator()(Args &&...args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <class F> constexpr decltype(auto) rec_lambda(F &&f) {
  return RecursiveLambda<F>(std::forward<F>(f));
}

using std::array;
using std::pair;
using std::tuple;
using std::vector;

template <class T>
using MinHeap = std::priority_queue<T, vector<T>, std::greater<T>>;

pair<int, vector<int>> compress(vector<int> deg, const int thres) {
  const int n = deg.size();
  UnionFind dsu(n);
  MinHeap<pair<int, int>> heap;
  for (const int i : rep(n)) {
    heap.emplace(deg[i], i);
  }
  while (heap.size() >= 2) {
    const auto [d1, u1] = heap.top();
    heap.pop();
    const auto [d2, u2] = heap.top();
    heap.pop();
    if (d1 + d2 > thres) {
      break;
    }
    const int v = dsu.merge(u1, u2).first;
    deg[v] = d1 + d2;
    heap.emplace(deg[v], v);
  }
  const auto groups = dsu.decompose();
  const int g = groups.size();
  vector<int> ret(n);
  for (const int i : rep(g)) {
    for (const int u : groups[i]) {
      ret[u] = i;
    }
  }
  return std::make_pair(g, std::move(ret));
}

void main_() {
  int L, R, M;
  std::cin >> L >> R >> M;
  vector<int> A(M), B(M);
  for (const int i : rep(M)) {
    std::cin >> A[i] >> B[i];
    A[i] -= 1, B[i] -= 1;
  }

  vector<int> degL(L), degR(R);
  for (const int x : A)
    degL[x] += 1;
  for (const int x : B)
    degR[x] += 1;

  int max_deg = 0;
  for (const int x : degL)
    setmax(max_deg, x);
  for (const int x : degR)
    setmax(max_deg, x);
  const int log2 = ceil_log2(max_deg);

  auto [sizeL, groupL] = compress(std::move(degL), 1 << log2);
  auto [sizeR, groupR] = compress(std::move(degR), 1 << log2);

  const int N = std::max(sizeL, sizeR);
  degL = degR = vector<int>(N);
  for (auto &x : A)
    degL[x = groupL[x]] += 1;
  for (auto &x : B)
    degR[x = groupR[x]] += 1;
  for (const int i : rep(N)) {
    for (const int _ : rep((1 << log2) - degL[i]))
      A.push_back(i);
    for (const int _ : rep((1 << log2) - degR[i]))
      B.push_back(i);
  }

  const int E = A.size();
  assert(E == (int)B.size());
  vector<int> ans(E);

  vector<char> used(E);
  vector<int> eid(E);
  std::iota(eid.begin(), eid.end(), 0);
  int color_id = 0;

  rec_lambda([&](auto &&self, vector<int> eid, const int level) -> void {
    if (level == 0) {
      color_id += 1;
      for (const int e : eid)
        ans[e] = color_id;
    } else {
      std::map<int, vector<pair<int, int>>> graph;
      for (const int e : eid) {
        graph[A[e]].emplace_back(e, B[e] + N);
        graph[B[e] + N].emplace_back(e, A[e]);
      }
      vector<int> left, right;
      const auto dfs = rec_lambda([&](auto &&self, const int u) -> void {
        auto &vec = graph[u];
        while (!vec.empty()) {
          const auto [e, v] = vec.back();
          vec.pop_back();
          if (used[e])
            continue;
          used[e] = true;
          self(v);
          (left.size() == right.size() ? left : right).push_back(e);
        }
      });
      for (const int e : eid)
        used[e] = false;
      for (const auto &[u, vec] : graph)
        dfs(u);
      self(std::move(left), level - 1);
      self(std::move(right), level - 1);
    }
  })(std::move(eid), log2);

  std::cout << (1 << log2) << '\n';
  for (const int i : rep(M))
    std::cout << ans[i] << '\n';
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  main_();
  return 0;
}

Compilation message

teoreticar.cpp: In function 'void main_()':
teoreticar.cpp:215:20: warning: unused variable '_' [-Wunused-variable]
  215 |     for (const int _ : rep((1 << log2) - degL[i]))
      |                    ^
teoreticar.cpp:217:20: warning: unused variable '_' [-Wunused-variable]
  217 |     for (const int _ : rep((1 << log2) - degR[i]))
      |                    ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 316 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1336 KB Output is correct
2 Correct 12 ms 1204 KB Output is correct
3 Correct 11 ms 1156 KB Output is correct
4 Correct 6 ms 972 KB Output is correct
5 Correct 6 ms 972 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1088 KB Output is correct
2 Correct 12 ms 1228 KB Output is correct
3 Correct 11 ms 1172 KB Output is correct
4 Correct 8 ms 1132 KB Output is correct
5 Correct 5 ms 716 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1783 ms 70120 KB Output is correct
2 Correct 2369 ms 65144 KB Output is correct
3 Correct 3814 ms 103368 KB Output is correct
4 Correct 1928 ms 76468 KB Output is correct
5 Correct 1540 ms 48496 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1825 ms 70164 KB Output is correct
2 Correct 3824 ms 103924 KB Output is correct
3 Correct 3100 ms 76120 KB Output is correct
4 Correct 1968 ms 75728 KB Output is correct
5 Correct 322 ms 13892 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1901 ms 75284 KB Output is correct
2 Correct 2962 ms 74432 KB Output is correct
3 Correct 209 ms 8592 KB Output is correct
4 Correct 1956 ms 52100 KB Output is correct
5 Correct 500 ms 37360 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2634 ms 66164 KB Output is correct
2 Correct 2134 ms 68432 KB Output is correct
3 Correct 2577 ms 69472 KB Output is correct
4 Correct 2667 ms 71332 KB Output is correct
5 Correct 1863 ms 75744 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1542 ms 49308 KB Output is correct
2 Correct 1695 ms 67472 KB Output is correct
3 Correct 2555 ms 68072 KB Output is correct
4 Correct 2599 ms 71348 KB Output is correct
5 Correct 1870 ms 48548 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1617 ms 49376 KB Output is correct
2 Correct 1757 ms 68444 KB Output is correct
3 Correct 3219 ms 78052 KB Output is correct
4 Correct 390 ms 13764 KB Output is correct
5 Correct 1813 ms 48628 KB Output is correct