algo2017_week6_huffman

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ALL(o) (o).begin(),(o).end()
#define fo(n) for(int i=0;i<n;i++)

struct node{
    char c;
    int n;
    node *l , *r;
    node(){ l = r = NULL; n = 0; c = 'x'; }
};

struct st{
    int n;
    node *r;
    st(){ n = 0; r = NULL; }
};

node *root = new node();
map<char,int> mp;

bool cmp( st a , st b ){ return a.n > b.n; }
bool cmp2( char a , char b ){ return mp[a] < mp[b]; }

vector<int> bit;

void dfs( node *now ){

    if( !now->l && !now->r ){
        int sum = 0 , t = 1;
        for( int i = bit.size() - 1 ; i > -1 ; --i ) sum += bit[i] * t , t *= 10;
        mp[now->c] = sum;
        return;
    }

    if( now->l ){
        bit.pb(0);
        dfs( now->l );
        bit.pop_back();
    }
    if( now->r ){
        bit.pb(1);
        dfs( now->r );
        bit.pop_back();
    }

    return;
}


int main(){

    string s;

    cin >> s;

    vector<char> p;

    fo( s.size() ){
        if( !mp[s[i]] ) p.pb( s[i] );
        mp[s[i]]++;
    }

    vector<st> q;

    fo( p.size() ){
        node *a = new node();
        a->c = p[i];
        a->n = mp[p[i]];

        st b;
        b.n = mp[p[i]];
        b.r = a;
        q.pb( b );
    }

    sort( ALL(q) , cmp );

    while( q.size() > 1 ){
        sort( ALL(q) , cmp );

        st a = q.back();
        q.pop_back();
        st b = q.back();
        q.pop_back();

        node *c = new node();

        c->n = a.n + b.n;
        c->l = a.n < b.n ? a.r : b.r;
        c->r = a.n < b.n ? b.r : a.r;

        st d;
        d.n = c->n;
        d.r = c;

        q.pb( d );
    }

    dfs( q[0].r );

    sort( ALL(p) , cmp2 );

    fo( p.size() ) printf("%c:%d\n" , p[i] , mp[p[i]]);

    return 0;
}