docker_space/frontier_cs_7/solution_try.cpp

#include <bits/stdc++.h>
using namespace std;

// Try: build the DAG using interval decomposition, but with additional 
// optimization: use multi-edges (multiple edges with same weight from same node)
// to split ranges and reuse more free chain nodes.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int L, R;
    cin >> L >> R;
    
    struct Edge { int to, w; };
    vector<vector<Edge>> adj;
    int n = 0;
    auto addNode = [&]() { adj.emplace_back(); return n++; };
    
    int END_NODE = addNode();
    int START = addNode();
    
    // Free chain
    map<int,int> freeNode;
    freeNode[0] = END_NODE;
    function<int(int)> getFree = [&](int k) -> int {
        if (freeNode.count(k)) return freeNode[k];
        int ch = getFree(k-1);
        int u = addNode();
        adj[u].push_back({ch, 0});
        adj[u].push_back({ch, 1});
        return freeNode[k] = u;
    };
    
    // Build range with potential multi-edge optimization
    map<tuple<int,int,int>, int> memo;
    
    function<int(int, int, int)> buildRange = [&](int k, int lo, int hi) -> int {
        if (lo > hi || k < 0) return -1;
        if (k == 0) return (lo == 0 && hi == 0) ? END_NODE : -1;
        if (lo == 0 && hi == (1 << k) - 1) return getFree(k);
        
        auto key = make_tuple(k, lo, hi);
        if (memo.count(key)) return memo[key];
        
        int mid = 1 << (k-1);
        
        // Standard split
        int left = -1, right = -1;
        if (lo <= min(hi, mid-1))
            left = buildRange(k-1, lo, min(hi, mid-1));
        if (max(lo, mid) <= hi)
            right = buildRange(k-1, max(lo, mid) - mid, hi - mid);
        
        if (left == -1 && right == -1) return memo[key] = -1;
        
        // Check if this node would be a single-edge (forced bit) node
        // If so, check if we can merge with the parent
        
        int u = addNode();
        if (left != -1) adj[u].push_back({left, 0});
        if (right != -1) adj[u].push_back({right, 1});
        
        return memo[key] = u;
    };
    
    int lenL = 32 - __builtin_clz(L);
    int lenR = 32 - __builtin_clz(R);
    
    for (int len = lenL; len <= lenR; len++) {
        int rs = 1 << (len-1), re = (1 << len) - 1;
        int cL = max(L, rs), cR = min(R, re);
        if (cL > cR) continue;
        
        int suffLen = len - 1;
        if (suffLen == 0) {
            adj[START].push_back({END_NODE, 1});
            continue;
        }
        
        int target = buildRange(suffLen, cL - rs, cR - rs);
        if (target >= 0)
            adj[START].push_back({target, 1});
    }
    
    // Now try to optimize: for each single-edge node, check if its parent
    // can absorb it by adding multi-edges.
    // This is a post-processing step.
    
    // Find single-edge nodes (not START, not END)
    // A single-edge node has exactly one outgoing edge.
    // Its parent has an edge to it. We want to replace:
    //   parent -> (w) -> single_node -> (w2) -> child
    // with:
    //   parent -> (w) -> new_node -> (w2) -> child
    // where new_node IS something else we can reuse.
    // But new_node would need the same remaining depth as single_node.
    // Since single_node's depth is unique, we can't reuse.
    
    // Alternative: absorb into parent using multi-edges.
    // parent -> (w) -> single_node -> (w2) -> child
    // Replace with: parent -> (w) -> child directly? NO - loses a bit.
    
    // We can't optimize single-edge nodes away.
    
    // Remove unreachable
    vector<bool> reach(n, false);
    queue<int> q;
    q.push(START); reach[START] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto& e : adj[u])
            if (e.to >= 0 && !reach[e.to]) { reach[e.to] = true; q.push(e.to); }
    }
    
    map<int,int> newId;
    int cnt = 0;
    newId[START] = ++cnt;
    for (int i = 0; i < n; i++)
        if (i != START && reach[i]) newId[i] = ++cnt;
    
    cout << cnt << "\n";
    vector<int> inv(cnt + 1);
    for (auto& [old, nw] : newId) inv[nw] = old;
    for (int i = 1; i <= cnt; i++) {
        int u = inv[i];
        cout << adj[u].size();
        for (auto& e : adj[u]) cout << " " << newId[e.to] << " " << e.w;
        cout << "\n";
    }
    
    return 0;
}