Submission #521265

#	Time	Username	Problem	Language	Result	Execution time	Memory
521265		KoD	Teoretičar (COCI18_teoreticar)	C++17	Compilation error	0 ms	0 KiB

teoreticar

#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 (stderr)

teoreticar.cpp:3:10: fatal error: proconlib/int_alias: No such file or directory
    3 | #include "proconlib/int_alias"
      |          ^~~~~~~~~~~~~~~~~~~~~
compilation terminated.