Proficient.
Put your skills to the test.

Problem summary

Encode a labelled cactus into bits and reconstruct exactly the same edge set in a separate process. A cactus is a connected simple undirected graph whose edges belong to at most one cycle. Shorter bit strings receive better scores.

Constraints

N=16000; T=5. Vertices 0…N−1. No loops or repeated edges. Score is the minimum over all subtests; bit thresholds 240000,256000,272000,304000,400000 have scores 1,0.76,0.60,0.44,0.14, with linear interpolation, then 0.14×400000/B.

Worked example

The official statement supplies the example graph but no output. The displayed 50 is this implementation’s local bit-count result, not an invented official expected output.

1
11 13
0 1
1 2
2 0
1 3
3 4
4 5
5 1
2 6
6 7
7 8
8 6
2 9
9 10

50

Solution analysis

1. Root an iterative depth-first search at vertex 0. Store the parent label of every other vertex. Each non-tree edge closes a path to an ancestor. Mark every tree edge along this cycle except its highest tree edge.
2. For each vertex v≠0, append its parent in ceil(log2 N) bits and one bit indicating whether its incoming tree edge is marked. Distinct cycles have disjoint edges, so their marked portions form disjoint nonempty directed paths. Their vertices may coincide at endpoints, but a marked incoming edge cannot have two marked child continuations.
3. The decoder first restores the tree. Every marked vertex with no marked child is the bottom of exactly one cycle path. Climb marked incoming edges until reaching the vertex top whose incoming edge is unmarked, then add the edge from the bottom to parent[top]. This reverses exactly the omitted closure.
4. For the example, a DFS may produce the tree paths 0−1−2 and 1−3−4−5 and 6−7−8. Mark the continuation edges within each cycle and recover closures 2−0,5−1,8−6. At N=11, width=4 and ten vertices use 50 bits. At N=16000 the fixed length is 15×15999=239985 bits; scoring follows the published length thresholds.

Why it works

In undirected DFS every non-tree edge joins a vertex to an ancestor. Its tree path forms its unique cycle. Edge disjointness of cactus cycles ensures no marked edge can be attributed to two cycles. Removing the highest edge of each cycle leaves a nonempty marked path because cycles have length at least three. Its unique bottom and upward chain identify both endpoints of the non-tree edge. Thus the decoder reconstructs every tree edge and every non-tree edge exactly once, preserving labels.

Watch out. Use iterative DFS to avoid a 16000-deep recursion. Never share graph information between encode and decode. Mark all but the highest cycle edge, not the whole cycle path. Parent labels must preserve original numbering.

Actual cactus.h grader interface. Encoder and decoder communicate exclusively through data; the local mock compares unordered normalized edge sets and reports the bit length.

#include"cactus.h"
#include<utility>
#include<vector>
std::vector<bool>encode(int n,std::vector<std::pair<int,int>>edges){
    std::vector<std::vector<int>>graph(n);
    for(auto edge:edges){
        graph[edge.first].push_back(edge.second);
        graph[edge.second].push_back(edge.first);
    }
    std::vector<int>parent(n,-1),depth(n),cursor(n),stack(1,0);
    std::vector<bool>marked(n,false);
    parent[0]=0;
    while(!stack.empty()){
        int u=stack.back();
        if(cursor[u]==static_cast<int>(graph[u].size())){
            stack.pop_back();
            continue;
        }
        int v=graph[u][cursor[u]++];
        if(v==parent[u]){
            continue;
        }
        if(parent[v]==-1){
            parent[v]=u;
            depth[v]=depth[u]+1;
            stack.push_back(v);
        }
        else if(depth[v]<depth[u]){
            // Leave the highest tree edge of this cycle unmarked.
            for(int w=u;parent[w]!=v;w=parent[w]){
                marked[w]=true;
            }
        }
    }
    int width=0;
    while((1<<width)<n){
        ++width;
    }
    std::vector<bool>data;
    for(int v=1;v<n;++v){
        for(int bit=0;bit<width;++bit){
            data.push_back((parent[v]>>bit)&1);
        }
        data.push_back(marked[v]);
    }
    return data;
}
std::vector<std::pair<int,int>>decode(int n,std::vector<bool>data){
    int width=0;
    while((1<<width)<n){
        ++width;
    }
    std::vector<int>parent(n),markedChildren(n);
    std::vector<bool>marked(n,false);
    std::vector<std::pair<int,int>>edges;
    int position=0;
    for(int v=1;v<n;++v){
        for(int bit=0;bit<width;++bit){
            parent[v]|=static_cast<int>(data[position++])<<bit;
        }
        marked[v]=data[position++];
        edges.push_back({v,parent[v]});
        if(marked[v]){
            ++markedChildren[parent[v]];
        }
    }
    for(int v=1;v<n;++v){
        if(marked[v]&&markedChildren[v]==0){
            int top=v;
            while(marked[top]){
                top=parent[top];
            }
            edges.push_back({v,parent[top]});
        }
    }
    return edges;
}