docker_space/frontier_cs_7/debug2.cpp

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

int main() {
    int L = 577837, R = 979141;

    struct Edge { int to, w; };
    vector<vector<Edge>> adj;
    int n = 0;
    auto nn = [&]() -> int { adj.emplace_back(); return n++; };

    int END = nn();
    int START = nn();

    map<int,int> fc;
    fc[0] = END;
    function<int(int)> getF = [&](int k) -> int {
        if (fc.count(k)) return fc[k];
        int ch = getF(k-1), u = nn();
        adj[u].push_back({ch, 0});
        adj[u].push_back({ch, 1});
        return fc[k] = u;
    };

    map<tuple<int,int,int>,int> rc;
    function<int(int,int,int)> gr = [&](int k, int lo, int hi) -> int {
        if (lo > hi) return -1;
        if (k == 0) return (lo == 0 && hi == 0) ? END : -1;
        if (lo == 0 && hi == (1<<k)-1) return getF(k);
        auto key = make_tuple(k, lo, hi);
        auto it = rc.find(key);
        if (it != rc.end()) return it->second;
        int mid = 1 << (k-1);
        int left = -1, right = -1;
        if (lo <= min(hi, mid-1))
            left = gr(k-1, lo, min(hi, mid-1));
        if (max(lo, mid) <= hi)
            right = gr(k-1, max(lo, mid) - mid, hi - mid);
        if (left == -1 && right == -1) return rc[key] = -1;
        int u = nn();
        if (left != -1) adj[u].push_back({left, 0});
        if (right != -1) adj[u].push_back({right, 1});
        return rc[key] = u;
    };

    int lenL = 32 - __builtin_clz(L), 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 target = (len == 1) ? END : gr(len-1, cL - rs, cR - rs);
        if (target != -1) adj[START].push_back({target, 1});
    }

    // Compute signatures bottom-up
    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 (!reach[e.to]) { reach[e.to] = true; q.push(e.to); }
        }
    }

    // Topological sort
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++) {
        if (!reach[u]) continue;
        for (auto& e : adj[u]) indeg[e.to]++;
    }
    vector<int> topo;
    for (int u = 0; u < n; u++)
        if (reach[u] && indeg[u] == 0) q.push(u);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (auto& e : adj[u]) if (--indeg[e.to] == 0) q.push(e.to);
    }
    reverse(topo.begin(), topo.end());

    // Compute canonical subtree signature
    map<vector<pair<int,int>>, vector<int>> sig_groups;
    vector<int> rep(n, -1);
    
    for (int u : topo) {
        if (!reach[u]) continue;
        vector<pair<int,int>> sig;
        for (auto& e : adj[u]) {
            sig.push_back({rep[e.to], e.w});
        }
        sort(sig.begin(), sig.end());
        
        if (sig_groups.count(sig)) {
            rep[u] = sig_groups[sig][0];
            sig_groups[sig].push_back(u);
        } else {
            rep[u] = u;
            sig_groups[sig] = {u};
        }
    }

    // Count unique reps
    set<int> unique_reps;
    for (int u = 0; u < n; u++)
        if (reach[u]) unique_reps.insert(rep[u]);
    
    cout << "Original reachable: " << count(reach.begin(), reach.end(), true) << endl;
    cout << "After merging: " << unique_reps.size() << endl;
    
    // Show groups with >1 member
    for (auto& [sig, group] : sig_groups) {
        if (group.size() > 1) {
            cout << "Merged group: ";
            for (int u : group) cout << u << " ";
            cout << " sig: ";
            for (auto& [c, w] : sig) cout << "(" << c << "," << w << ")";
            cout << endl;
        }
    }

    return 0;
}