File size: 5,014 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 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 | #include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <tuple>
using namespace std;
// Structure to represent an edge in the graph
struct Edge {
int to;
int weight;
};
// Structure to represent a node in the graph
struct Node {
vector<Edge> out;
};
int main() {
// Optimize I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int L, R;
if (!(cin >> L >> R)) return 0;
vector<Node> nodes;
// Add Sink node at index 0 (will be output as ID 1)
// The sink node has 0 outgoing edges and represents the end of a valid path
nodes.push_back(Node{});
// Build H-chain
// H[i] is a node that accepts all binary strings of length i.
// H[0] is the Sink node (index 0).
// H[i] has edges with weight 0 and 1 to H[i-1].
// Since R <= 10^6 < 2^20, the maximum bit length needed is 20.
vector<int> H(21);
H[0] = 0;
for (int i = 1; i <= 20; ++i) {
int idx = nodes.size();
nodes.push_back(Node{});
nodes[idx].out.push_back({H[i-1], 0});
nodes[idx].out.push_back({H[i-1], 1});
H[i] = idx;
}
// Start node creation
int start_node = nodes.size();
nodes.push_back(Node{});
// Helper lambda to calculate bit length of an integer
auto get_len = [](int x) {
if (x == 0) return 0;
int len = 0;
while ((1LL << len) <= x) len++;
return len;
};
int l_len = get_len(L);
int r_len = get_len(R);
// Memoization map to share nodes for identical sub-ranges
// Key: {lower bound, upper bound, height} -> Value: node index
map<tuple<int, int, int>, int> memo;
// Recursive function to build the DAG structure for a specific range of suffixes
// range: [lower, upper] relative to current subtree
// height: number of bits remaining
auto build_range = [&](auto&& self, int lower, int upper, int height) -> int {
// Optimization: If the requested range covers the full set of strings of this height,
// return the pre-built H node.
long long range_size = 1LL << height;
if (lower == 0 && upper == range_size - 1) {
return H[height];
}
// Base case: height 0 (should be handled by H[0] check above, but for safety)
if (height == 0) return H[0];
// Check memoization
auto key = make_tuple(lower, upper, height);
if (memo.count(key)) return memo[key];
// Create new node
int curr = nodes.size();
nodes.push_back(Node{});
memo[key] = curr;
long long half = 1LL << (height - 1);
// Process 0-branch (MSB is 0)
// Intersection of [lower, upper] with [0, half-1]
int l0 = max((long long)lower, 0LL);
int u0 = min((long long)upper, half - 1);
if (l0 <= u0) {
// Recurse with range unchanged (relative to next bit)
int child0 = self(self, l0, u0, height - 1);
nodes[curr].out.push_back({child0, 0});
}
// Process 1-branch (MSB is 1)
// Intersection of [lower, upper] with [half, 2*half-1]
// Normalize range by subtracting half
int l1 = max((long long)lower, half) - half;
int u1 = min((long long)upper, 2 * half - 1) - half;
if (l1 <= u1) {
int child1 = self(self, l1, u1, height - 1);
nodes[curr].out.push_back({child1, 1});
}
return curr;
};
// Iterate over all possible bit lengths in [L, R]
for (int len = l_len; len <= r_len; ++len) {
// Calculate the range of numbers with length 'len' that are within [L, R]
long long min_val = 1LL << (len - 1);
long long max_val = (1LL << len) - 1;
long long A = max((long long)L, min_val);
long long B = min((long long)R, max_val);
if (A <= B) {
// We need to match suffixes of length (len-1)
// The leading '1' is handled by the edge from Start
int suffix_height = len - 1;
// Normalize range to be 0-based relative to the suffixes
int lower = A - min_val;
int upper = B - min_val;
// Build/Get the node representing these suffixes
int target = build_range(build_range, lower, upper, suffix_height);
// Add edge from Start node with weight 1
nodes[start_node].out.push_back({target, 1});
}
}
// Output the graph
// Format:
// N
// For each node 1..N: K a1 v1 a2 v2 ...
// Note: Internal 0-based indices are converted to 1-based for output
cout << nodes.size() << "\n";
for (int i = 0; i < nodes.size(); ++i) {
cout << nodes[i].out.size();
for (auto& edge : nodes[i].out) {
cout << " " << edge.to + 1 << " " << edge.weight;
}
cout << "\n";
}
return 0;
} |