Cod sursa(job #2206927)

Utilizator bt.panteaPantea Beniamin bt.pantea Data 24 mai 2018 15:34:26
Problema Coduri Huffman Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#define NMAX 1000005

using namespace std;

ifstream f("huffman.in");
ofstream g("huffman.out");

priority_queue< pair < int, int > > Q;

struct Node 
{
    int value;
    int next[2];
}node[2*NMAX];

int n, lg, k, root, level[2 * NMAX];
int cod[2 * NMAX];

void calcLevel(int k, int nivel, int c)
{
    level[k] = nivel;
    cod[k] = c;
    if (node[k].next[0] != 0)
    {
        calcLevel(node[k].next[0], nivel + 1, 2 * c);
        calcLevel(node[k].next[1], nivel + 1, 2 * c + 1);
    }
}

void solve()
{
    k = n;

    while (Q.size() >= 2)
    {
        pair < int, int > x1, x2;
        x1 = Q.top();
        Q.pop();
        x2 = Q.top();
        Q.pop();
        int i = x1.second, j = x2.second;
        k++;
        node[k].value = - x1.first - x2.first;
        node[k].next[0] = i;
        node[k].next[1] = j;
        Q.push({-node[k].value, k});
    }
    root = Q.top().second; // root = 2 * n - 1;
}

void read()
{
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        f >> node[i].value;
        node[i].next[0] = node[i].next[1] = 0;
        Q.push({-node[i].value, i});
    }
}

int main()
{
    read();
    solve();
    calcLevel(root, 0, 0);

    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += node[i].value * level[i];
    g << sum <<'\n';

    for (int i = 1; i <= n; i++)
        g << level[i] << ' ' << cod[i] << '\n';
    return 0;
}