#include <bits/stdc++.h>
#define ENABLE_AVX2
#include "proconlib/int_alias"
#include "proconlib/rep"
#include "proconlib/union_find"
#include "proconlib/ceil_log2"
#include "proconlib/setmax"
#include "proconlib/rec_lambda"
using std::vector;
using std::array;
using std::pair;
using std::tuple;
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:3:10: fatal error: proconlib/int_alias: No such file or directory
3 | #include "proconlib/int_alias"
| ^~~~~~~~~~~~~~~~~~~~~
compilation terminated.
