Cod sursa(job #2729194)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 24 martie 2021 13:35:54
Problema Coduri Huffman Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "huffman.in" );
ofstream fout( "huffman.out" );

const int NMAX = 1000005;

int n;
int frec[NMAX];
priority_queue < pair<int, int> > H;
int lf[2 * NMAX], rg[2 * NMAX];
string current;
long long lg;
long long val[NMAX];
int sz[NMAX];

long long Str_to_Int( string s ) {
    long long ans = 0;
    long long _aux = 1;

    for( int i = s.size() - 1; i >= 0; --i ) {
        ans += ( s[i] == '1' ) * _aux;
        _aux = ( _aux << 1 );
    }
    return ans;
}

void Dfs( int nod ) {
    if( lf[nod] == 0 && rg[nod] == 0 ) {

        lg += 1LL * frec[nod] *  current.size();
        val[nod] = Str_to_Int( current );
        sz[nod] = current.size();
        return;
    }

    current.push_back( '0' );
    Dfs( lf[nod] );
    current.pop_back();

    current.push_back( '1' );
    Dfs( rg[nod] );
    current.pop_back();
}

int main()
{
    fin >> n;

    for( int i = 1; i <= n; ++i ) {
        fin >> frec[i];
        H.push( { -frec[i], i } );
    }

    int nr_nodes = n;
    while( H.size() > 1 ) {
        int nod1, c1, nod2, c2;

        nod1 = H.top().second;
        c1 = H.top().first;
        H.pop();

        nod2 = H.top().second;
        c2 = H.top().first;
        H.pop();

        ++nr_nodes;
        lf[nr_nodes] = nod1;
        rg[nr_nodes] = nod2;

        H.push( { c1 + c2, nr_nodes } );
    }

    //for( int i = 1; i <= nr_nodes; ++i )
    //    fout << i << ' ' << lf[i] << '\n' << i << ' ' << rg[i] << '\n';

    int root = H.top().second;

    Dfs( root );

    fout << lg << '\n';
    for( int i = 1; i <= n; ++i )
        fout << sz[i] << ' ' << val[i] << '\n';

    fin.close();
    fout.close();

    return 0;
}