File size: 4,288 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | #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;
}
|