1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <map>
5

6
struct HuffmanNode
7
{
8
    std::string word;
9
    unsigned long long count;
10
    HuffmanNode* left;
11
    HuffmanNode* right;
12
    HuffmanNode* parent;
13
    bool operator<(const HuffmanNode& other) const
14
    {
15
        return count > other.count; // For min-heap
16
    }
17
};
18

19
struct Cmp {
20
    bool operator()(HuffmanNode* a, HuffmanNode* b) const {
21
        return a->count > b->count; // min-heap by count
22
    }
23
};
24

25
static std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Cmp> pq;
26
static std::vector<std::string> words;
27
static std::map<std::string, std::string> wordCode;
28

29
void anal(HuffmanNode* node, std::string code = "")
30
{
31
    if(node->left == nullptr && node->right == nullptr)
32
    {
33
        wordCode[node->word] = code;
34
        return;
35
    }
36
    anal(node->left, code + "0");
37
    anal(node->right, code + "1");
38
}
39
void del(HuffmanNode* node)
40
{
41
    if(node == nullptr) return;
42
    del(node->left);
43
    del(node->right);
44
    node = nullptr;
45
    delete node;
46
}
47

48
int main()
49
{
50
    int n;
51
    std::cin >> n;
52
    if(n == 1)
53
    {
54
        std::string word;
55
        int count;
56
        std::cin >> word >> count;
57
        std::cout << word << " " << "0" << std::endl;
58
        return 0;
59
    }
60
    for(int index = 0;index < n;index++)
61
    {
62
        std::string word;
63
        unsigned long long count;
64
        std::cin >> word >> count;
65
        words.push_back(word);
66
        wordCode[word] = "";
67
        pq.push(new HuffmanNode{word, count, nullptr, nullptr, nullptr});
68
    }
69
    while(pq.size() > 1)
70
    {
71
        HuffmanNode* w1 = pq.top();
72
        pq.pop();
73
        HuffmanNode* w2 = pq.top();
74
        pq.pop();
75
        HuffmanNode* node = new HuffmanNode{w1->word + w2->word, w1->count + w2->count, w1, w2, nullptr};
76
        w1->parent = node;
77
        w2->parent = node;
78
        pq.push(node);
79
    }
80
    HuffmanNode* root = pq.top();
81
    pq.pop();
82
    anal(root);
83
    for(auto& word : words)
84
    {
85
        std::cout << word << " " << wordCode[word] << std::endl;
86
    }
87
    del(root);
88
    return 0;
89
}