examen-2012

balance.cxx

#include <cstdint>
#include <cstddef>
#include <iostream>
#include <iterator>
//g++ -std=c++0x balance.cxx -o balance_cxx -O4 -march=native
int main(int argc, char* argv[]) {
  for(std::istream_iterator<int64_t> in(std::cin),e; in!=e && *in; ){
    int64_t res(0);
    for(int64_t i(0),nb(*in++); i != nb; ++i,++in)
      { res+= (i < (nb /2)) ? *in : ((i > (nb /2) ||(nb %2 == 0 )) ? -*in :0); }
    std::cout<<((res == 0)? "equal":(( res > 0 )? "left":"right"))<<std::endl;
  }
  return 0;
}

crazy-lazy.cxx

#include <string>
#include <iostream>
#include <strstream>
#include <utility>
#include <iterator>
#include <cstring>
#include <cstdint>
#include <vector>
#include <sys/time.h>
#include <unistd.h>

void affiche(const char *s,struct timeval tvStart, struct timeval tvStop){
  long int diff = tvStop.tv_usec - tvStart.tv_usec;
  if (diff < 0) 
    diff += 1000000;
  printf("%s: %ld microseconds\n",s,diff);
}

// g++-snapshot -std=c++11 crazy-lazy.cxx -o crazy-lazy -O4 -march=native  -ftree-vectorizer-verbose=3
// clang++ -std=c++11 crazy.cxx -o crazy  -O4 -march=native
/*
for storing edges a  radix sorted vector
Cheating : exploiting 8 chars names and assuming ASCII strict (7 bits) and cost <=30 (255 actually)
for disjoint sets https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Could remove unordered map by storing ptr to city struct instead of the int name. The city struct would contain city name, representative city ptr and set size cf knuth standford graph miles_span.pdf p8

*/
// 8 chars for city names ?
// if ASCII, I can use std::int64_t !

union name_t {
  int64_t as_int;
  char as_chars[8];
};

struct city {
  name_t name;
  city(int64_t n){name.as_int=n; component_repr=this; component_size=1;}
  city* next_hashlist;
  city* component_repr;
  std::size_t component_size;
  static std::vector<city*> hash_map;
  static std::vector<city> cities;
  static city* get(int64_t name){
    //    int16_t const key(name ^ (name >> 16) ^ (name >> 32) ^ (name >> 40));
    int32_t const keytmp(name ^ (name >> 32));
    int16_t const key(keytmp ^ (keytmp >> 16));
    city* ptr= hash_map[key];
    while(ptr && ( ptr->name.as_int != name)) { ptr= ptr->next_hashlist; }
    if(!ptr){
      cities.push_back(city(name));
      cities.back().next_hashlist= hash_map[key];
      cities.back().component_repr= &cities.back();
      ptr= hash_map[key]= &cities.back();
    }
    return ptr;
  }
  city* repr(){
    if(component_repr != this){component_repr= component_repr->repr();}
    return component_repr;
  }
  void link_with(city* other){ // we already have repr and they are different
    if(component_size < other->component_size){ component_repr= other;}
    else if (component_size > other->component_size) {other->component_repr= this;}
    else {
      other->component_repr= this;
      ++component_size;
    }
  }
};

std::vector<city*> city::hash_map= std::vector<city*>(0xFFFF+1, 0);
std::vector<city> city::cities;

struct edge {

  std::pair<city*, city*> parse(){
    name_t name;
    name.as_int=0;
    char const*next = (char const*)rawmemchr(to_parse,' ');
    memcpy(name.as_chars, to_parse, (next-to_parse));
    city* c1(city::get(name.as_int));
    char const* next_name(next+1);
    next =  (char const*)rawmemchr(next_name,' ');
    memcpy(name.as_chars, next_name, (next-next_name));
    return std::make_pair(c1, city::get(name.as_int));
  }
  int cost;
  edge* next=0;
  char const* to_parse;
};
//  https://en.wikipedia.org/wiki/Disjoint-set_data_structure
std::vector<edge> edges_store;
// array of lists of edges of the same cost(= array index), first is head, second is tail
std::vector<std::pair<edge*, edge*> > edges_todo(100, std::pair<edge*, edge*>(0,0));

void read_edges(char const* buff_it, std::size_t buff_size, std::size_t nb_links){
  edges_store.resize(nb_links);
  for(std::size_t i(0); i != nb_links; ++i, ++buff_it){
    edge& e(edges_store[i]);
    e.to_parse= buff_it;
    buff_it=(char const*)rawmemchr(buff_it, '\n');
    e.cost= (buff_it[-1]- '0') + ((buff_it[-2] == ' ') ?  0 : (10*(buff_it[-2]- '0')));
    if(edges_todo[e.cost].first){
      e.next=edges_todo[e.cost].first;
      edges_todo[e.cost].first=&e;
    }else{ edges_todo[e.cost].first=edges_todo[e.cost].second=&e; }
  }
  {
    int i,j,res;
    for(res=0; (res!= edges_todo.size()) && !(edges_todo[res].first); ++res) {}
    for(i=res; i!=edges_todo.size() ; i=j) {
      for(j=i+1; (j!= edges_todo.size()) && !(edges_todo[j].first) ; ++j) {}
      edges_todo[i].second->next=edges_todo[j].first;
    }
    edges_todo[0]= edges_todo[res];
  }
}


int main(int argc, char* argv[]) {
  struct timeval tv_start,tv_inter,tv_end;
  gettimeofday(&tv_start,NULL);

  std::size_t nb_cities, nb_links;
// EDIT: OK you want to play by C rules, I'll bite ! :)
// must use std::strstream as std::istringstream makes a copy :(
  const std::size_t max_nb_chars_city_name(8), max_nb_chars_cost(2);
  std::cin >> nb_cities >> nb_links;

  const std::size_t buff_size(nb_links*((max_nb_chars_city_name+1)*2
                                        + max_nb_chars_cost+1)+1);
  char* buff= new char[buff_size];
  std::cin.read(buff, buff_size);
  std::size_t actual_size(std::cin.gcount());
  //skip \n
  read_edges((char const*)buff+1, actual_size, nb_links);
  gettimeofday(&tv_inter,NULL);
  affiche("reading ",tv_start,tv_inter);
  city::cities.reserve(nb_cities);
  std::size_t total(0), merges_done(1);  // start at 1 because we need nb-1 merges to have one last set
  for(edge* e_it(edges_todo[0].first); (merges_done != nb_cities) && e_it; e_it= e_it->next) {
    std::pair<city*, city*> cities(e_it->parse());
    city* repr1(cities.first->repr());
    city* repr2(cities.second->repr());
    if(repr1 != repr2){
      repr1->link_with(repr2);
      total+= e_it->cost;
      ++merges_done;
    }
  }
  std::cout << total << std::endl;
  gettimeofday(&tv_end,NULL);
  affiche("MST algorithm",tv_inter,tv_end);
  affiche("TOTAL",tv_start,tv_end);
  return 0;
}

good-bad-ugly.clj

":";exec java -cp "/usr/share/java/clojure.jar" clojure.main $0 $*
(ns good-or-bad-2012)
(let [good-bad-ugly (fn [str]
                      (let [c (reduce
                               #(+ %1 (condp = %2, \g 1, \G 1, \b -1, \B -1, 0))
                                      0 (seq str))]
                        (cond (< c 0) "BAD", (> c 0) "GOOD", :else "UGLY")))]
  (dorun (->> *in* java.io.BufferedReader. line-seq (drop 1)
               (map #(println %1 " is " (good-bad-ugly %1))))))

good-bad-ugly.cxx

#include<iostream>

int main(int argc, char* argv[]) {
  int nb;
  std::cin >> nb; std::cin.get();//eat trailing \n
  for(int i(0); i != nb; ++i){
    int res(0);
    for(char c; (c=std::cin.get()) != '\n'; std::cout << c){
      switch(c) {
      case 'b': case 'B': { --res; break;}
      case 'g': case 'G': { ++res; break;}
      }
    }
    std::cout<<" is "<<((res == 0)?"UGLY":((res < 0)?"BAD":"GOOD"))<< std::endl;
  }
  return 0;
}

iptv.cxx

#include <string>
#include <iostream>
#include <unordered_set>
#include <list>
#include <iterator>
#include <algorithm>
#include <queue>
#include <chrono>
// g++-snapshot -std=c++11 my_first_take.cxx -o my_first_take -O4 -march=native
/* optimization options are *very* important :
On my laptop with Intel CPU Atom N550 
without the options:
data file parsed in 651 ms.
2587
minimum spanning tree computed in 2782 ms.

with -O4 -march=native:
data file parsed in 437 ms.
2587
minimum spanning tree computed in 296 ms.
*/
/* should use boost::graph
 or special purpose data structure for disjoint sets

for storing nodes if I have to make my own disjoint sets data structure, I'd use binomial heaps because they can be searched efficiently for a node and merged efficiently. Baring a binomial heap implementation, it is possible to use:
- heaps for efficient search, but slow merge
- unordered lists for slow search, but fast merge (splice)

for storing edges a  C++11 priority_queue

for efficient nodes compares, we intern the city names and use pointers to the interned canonical strings.
*/
// for interning
std::unordered_set<std::string> city_names;

// undirected ->could reorder nodes
struct edge {
  // as priority queue returns the max elts, we simply use > for operator< to get the min elt
  bool operator<(edge const& o)const{ return cost > o.cost;}
  std::string const* n1;
  std::string const* n2;
  std::size_t cost;
};

template<typename IStream > IStream& operator>>(IStream& is, edge& e){
  std::string tmp;
  bool ok(false);
  if(is >> tmp) {
    e.n1= &(*(city_names.insert(tmp).first));
    if(is >> tmp) {
      e.n2= &((*city_names.insert(tmp).first));
      if(is >> e.cost){
        ok= true;
      }
    }
  }
  if(!ok){ is.setstate(std::ios::failbit);}
  return is;
}

template<typename V>
struct disjoint_sets {
  // could be single linked lists
  typedef std::list<V> subset_t;
  typedef std::list<subset_t> set_t;
  template<typename It>
  disjoint_sets(It b, It e){
    // we get iterators to std::string, not the std::string const* that V is
    std::transform(b, e, std::back_inserter(s)
                   ,[]( typename std::iterator_traits<V>::value_type const& str)
                   {return subset_t(1, &str);});
  }
  // returns true in case of a merge
  bool merge_if_distinct(V const& v1, V const& v2) {
    typename set_t::iterator it1(s.end()), it2(s.end());
    for(typename set_t::iterator it(s.begin())
          ; it != s.end() && (it1 == s.end() || it2 == s.end()); ++it) {
      for(typename subset_t::iterator sit(it->begin())
            ; (sit != it->end()) && (it1 == s.end() || it2 == s.end()); ++sit) {
        if(*sit == v1) { it1= it; }
        if(*sit == v2) { it2= it; }
      }
    }
    if(it1 == it2) { return false;}
    it1->splice(it1->begin(), *it2);
    s.erase(it2);
    return true;
  }
  // cannot use size() to know if only one elt left as size() shouldn't be efficient since splice is. The caller will count the merges.
  set_t s;
};

int main(int argc, char* argv[]) {
  // these are not needed in fact, it's 2012 already !
  std::size_t nb_cities, nb_links;
  typedef std::chrono::high_resolution_clock clock_t;
  typedef std::chrono::milliseconds milliseconds_t;
  std::chrono::time_point<clock_t> const start(clock_t::now());
  std::cin >> nb_cities >> nb_links;

  std::istream_iterator<edge> b(std::cin), end;
  std::priority_queue<edge> edges_todo;
  std::for_each(b, end 
                ,[&edges_todo](edge const& ed){edges_todo.push(ed);});
  std::chrono::time_point<clock_t> const parsed(clock_t::now());
  std::cerr<<"data file parsed in "<<std::chrono::duration_cast<milliseconds_t>(parsed-start).count()<<" ms."<<std::endl;
  disjoint_sets<std::string const*> trees(city_names.begin(), city_names.end());
  std::size_t total(0);
  // start at 1 because we need nb-1 merges to have one last set
  for(std::size_t merges_done(1); merges_done != city_names.size()
        ; edges_todo.pop()) {
    edge const& t(edges_todo.top());
    if(trees.merge_if_distinct(t.n1, t.n2)){
      total+= t.cost;
      ++merges_done;
    }
  }
  std::cout << total << std::endl;
  std::chrono::time_point<clock_t> const finished(clock_t::now());
  std::cerr<<"minimum spanning tree computed in "<<std::chrono::duration_cast<milliseconds_t>(finished-parsed).count()<<" ms."<<std::endl;
  return 0;
}

iptv_boost.cxx

#include <string>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <iterator>
#include <algorithm>
#include <queue>
#include <chrono>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/property_map/property_map.hpp>
// g++-snapshot -std=c++11 iptv_boost.cxx -o iptv_boost -O4 -march=native
/* should use boost::graph
 or special purpose data structure for disjoint sets

for storing nodes if I have to make my own disjoint sets data structure, I'd use binomial heaps because they can be searched efficiently for a node and merged efficiently. Baring a binomial heap implementation, it is possible to use:
- heaps for efficient search, but slow merge
- unordered lists for slow search, but fast merge (splice)

for storing edges a  C++11 priority_queue

for efficient nodes compares, we intern the city names and use pointers to the interned canonical strings.
*/
// for interning
std::unordered_set<std::string> city_names;

// undirected ->could reorder nodes
struct edge {
  // as priority queue returns the max elts, we simply use > for operator< to get the min elt
  bool operator<(edge const& o)const{ return cost > o.cost;}
  std::string const* n1;
  std::string const* n2;
  std::size_t cost;
};

template<typename IStream > IStream& operator>>(IStream& is, edge& e){
  std::string tmp;
  bool ok(false);
  if(is >> tmp) {
    e.n1= &(*(city_names.insert(tmp).first));
    if(is >> tmp) {
      e.n2= &((*city_names.insert(tmp).first));
      if(is >> e.cost){
        ok= true;
      }
    }
  }
  if(!ok){ is.setstate(std::ios::failbit);}
  return is;
}

int main(int argc, char* argv[]) {
  // these are not needed in fact, it's 2012 already !
  std::size_t nb_cities, nb_links;
  typedef std::chrono::high_resolution_clock clock_t;
  typedef std::chrono::milliseconds milliseconds_t;
  std::chrono::time_point<clock_t> const start(clock_t::now());
  std::cin >> nb_cities >> nb_links;

  std::istream_iterator<edge> b(std::cin), end;
  std::priority_queue<edge> edges_todo;
  std::for_each(b, end 
                ,[&edges_todo](edge const& ed){edges_todo.push(ed);});
  std::chrono::time_point<clock_t> const parsed(clock_t::now());
  std::cerr<<"data file parsed in "<<std::chrono::duration_cast<milliseconds_t>(parsed-start).count()<<" ms."<<std::endl;

  typedef std::unordered_map<std::string const*,std::size_t> rank_t; // => order on Element
  typedef std::unordered_map<std::string const*,std::string const*> parent_t;
  rank_t rank_map;
  parent_t parent_map;

  boost::associative_property_map<rank_t>   rank_pmap(rank_map);
  boost::associative_property_map<parent_t> parent_pmap(parent_map);
  boost::disjoint_sets<boost::associative_property_map<rank_t>
                       ,boost::associative_property_map<parent_t> > trees(rank_pmap, parent_pmap);
  std::for_each(city_names.begin(), city_names.end(), [&trees](std::string const& c){trees.make_set(&c);});
  std::size_t total(0);
  // start at 1 because we need nb-1 merges to have one last set
  for(std::size_t merges_done(1); merges_done != city_names.size()
        ; edges_todo.pop()) {
    edge const& t(edges_todo.top());
    auto s1(trees.find_set(t.n1)), s2(trees.find_set(t.n2));
    if(s1 != s2) {
      trees.link(s1, s2);
      total+= t.cost;
      ++merges_done;
    }
  }
  std::cout << total << std::endl;
  std::chrono::time_point<clock_t> const finished(clock_t::now());
  std::cerr<<"minimum spanning tree computed in "<<std::chrono::duration_cast<milliseconds_t>(finished-parsed).count()<<" ms."<<std::endl;
  return 0;
}

iptv_buffered_read.cxx

#include <string>
#include <iostream>
#include <strstream>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <list>
#include <iterator>
#include <algorithm>
#include <queue>
#include <chrono>


// g++-snapshot -std=c++11 my_third_take.cxx -o my_third_take -O4 -march=native
/*
for storing edges a  C++11 priority_queue
for efficient nodes compares, we intern the city names and use pointers to the interned canonical strings.
for disjoint sets https://en.wikipedia.org/wiki/Disjoint-set_data_structure
*/
// for interning
std::unordered_set<std::string> city_names;

// undirected ->could reorder nodes
struct edge {
  // as priority queue returns the max elts, we simply use > for operator< to get the min elt
  bool operator<(edge const& o)const{ return cost > o.cost;}
  std::string const* n1;
  std::string const* n2;
  std::size_t cost;
};

template<typename IStream > IStream& operator>>(IStream& is, edge& e){
  std::string tmp;
  bool ok(false);
  if(is >> tmp) {
    e.n1= &(*(city_names.insert(tmp).first));
    if(is >> tmp) {
      e.n2= &((*city_names.insert(tmp).first));
      if(is >> e.cost){
        ok= true;
      }
    }
  }
  if(!ok){ is.setstate(std::ios::failbit);}
  return is;
}

//  https://en.wikipedia.org/wiki/Disjoint-set_data_structure
template<typename V>
struct disjoint_sets{
  typedef std::pair<V, std::size_t> parent_rank_t;
  std::unordered_map<V,parent_rank_t> data;

  void make_set(V const& v)
  { data[v]=std::make_pair(v, 1); }

  V find_set(V const& v)  {
    V & p(data[v].first);
    if(p != v) {p= find_set(p);}
    return p;
  }

  void link(V const& v1, V const& v2) {
    V root1(find_set(v1)), root2(find_set(v2));
    if(root1 == root2) { return; }
    parent_rank_t & p1(data[root1]);
    parent_rank_t & p2(data[root2]);
    if(p1.second < p2.second) { p1.first= root2; }
    else if (p1.second > p2.second) {p2.first= root1; }
    else {
      p2.first= root1; 
      ++p1.second;
    }
  }
};


int main(int argc, char* argv[]) {
  // these are not needed in fact, it's 2012 already !
  std::size_t nb_cities, nb_links;
// EDIT: OK you want to pay by C rules, I'll bite ! :)
// must use std::strstream as std::istringstream makes a copy :(
const std::size_t max_nb_chars_city_name(8), max_nb_chars_cost(2);
  typedef std::chrono::high_resolution_clock clock_t;
  typedef std::chrono::milliseconds milliseconds_t;
  std::chrono::time_point<clock_t> const start(clock_t::now());
  std::cin >> nb_cities >> nb_links;
  const std::size_t buff_size(nb_links*((max_nb_chars_city_name+1)*2
                                        + max_nb_chars_cost+1)+1);

  char* buff= new char[buff_size];
  std::cin.read(buff, buff_size);
  std::istrstream buff_stream(buff);
  std::istream_iterator<edge> b(buff_stream), end;
  std::priority_queue<edge> edges_todo;
  std::for_each(b, end 
                ,[&edges_todo](edge const& ed){edges_todo.push(ed);});
  delete [] buff;
  std::chrono::time_point<clock_t> const parsed(clock_t::now());
  std::cerr<<"data file parsed in "<<std::chrono::duration_cast<milliseconds_t>(parsed-start).count()<<" ms."<<std::endl;
  disjoint_sets<std::string const*> trees;
  std::for_each(city_names.begin(), city_names.end(), [&trees](std::string const& c){trees.make_set(&c);});
  std::size_t total(0);
  // start at 1 because we need nb-1 merges to have one last set
  for(std::size_t merges_done(1); merges_done != city_names.size()
        ; edges_todo.pop()) {
    edge const& t(edges_todo.top());
    auto s1(trees.find_set(t.n1)), s2(trees.find_set(t.n2));
    if(s1 != s2) {
      trees.link(s1, s2);
      total+= t.cost;
      ++merges_done;
    }
  }
  std::cout << total << std::endl;
  std::chrono::time_point<clock_t> const finished(clock_t::now());
  std::cerr<<"minimum spanning tree computed in "<<std::chrono::duration_cast<milliseconds_t>(finished-parsed).count()<<" ms."<<std::endl;
  return 0;
}

iptv_crazy.cxx

#include <string>
#include <iostream>
#include <strstream>
#include <unordered_map>
#include <utility>
#include <iterator>
#include <algorithm>
#include <chrono>
#include <cstdint>

// g++-snapshot -std=c++11 iptv_crazy.cxx -o iptv_crazy -O4 -march=native  -ftree-vectorizer-verbose=3
// clang++ -std=c++11 iptv_crazy.cxx -o iptv_crazy  -O4 -march=native
/*
for storing edges a  radix sorted vector
Cheating : exploiting 8 chars names and assuming ASCII strict (7 bits) and cost <=30 (255 actually)
for disjoint sets https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Could remove unordered map by storing ptr to city struct instead of the int name. The city struct would contain city name, representative city ptr and set size cf knuth standford graph miles_span.pdf p8

*/


std::vector<int64_t> unique_names;
// undirected ->could reorder nodes
struct /*alignas(16)*/ edge {
  // as priority queue returns the max elts, we simply use > for operator< to get the min elt
  int64_t n1 __attribute__ ((__aligned__(16)));
  int64_t n2_cost;
};
int64_t read_name(char *& c){
  int64_t res(0);
  for(int i(0); i!=8 && (*c != ' '); ++i, ++c, res<<=7 )
    { res|= *c; }
  res<<=1;// now we have 8 clear bits as LSB
  unique_names.push_back(res);
  return res;
}

void make_names_unique(){
  // 7 significant bytes, byte 0 is clear we skip it
  std::vector<std::size_t> names_buckets(257*7, 0);
  std::vector<int64_t> tmp_names(unique_names.size());
  for(std::size_t i(0); i != unique_names.size(); ++i){
    for(int n_byte(0); n_byte != 7; ++n_byte)
      { ++names_buckets[257*n_byte +1+ ((unique_names[i]>>(8*(n_byte+1))) & 0xFF)]; }
  }
  for(int n_byte(0); n_byte != 7; ++n_byte){
    for(int i(1); i!=257; ++i){ names_buckets[257*n_byte+ i] += names_buckets[257*n_byte+ i-1]; }
  }
  for(int n_byte(0); n_byte != 7; ++n_byte, unique_names.swap(tmp_names)){
    for(std::size_t i(0); i != unique_names.size(); ++i)
      { tmp_names[names_buckets[257*n_byte + ((unique_names[i]>>(8*(n_byte+1))) & 0xFF)]++] = unique_names[i];}
  }
  // data ordered back into unique_names, now make_it unique
  unique_names.resize(std::distance(unique_names.begin()
                                    ,std::unique(unique_names.begin(), unique_names.end())));
}


template<typename CharIt, typename CharSize, typename EdgesIt, typename EdgesSize>
void read_edges(CharIt buff_it, CharSize buff_size, EdgesIt edges_out, EdgesSize nb_links){
  std::vector<edge> edges_to_sort(nb_links);
  std::vector<std::size_t> buckets(257, 0);// could be 31+1 (instead of 256+1)per spec
  
  for(std::size_t i(0); i != nb_links; ++i, ++buff_it){
    edges_to_sort[i].n1 = read_name(buff_it);
    ++buff_it;// skip ' '
    edges_to_sort[i].n2_cost = read_name(buff_it);
    ++buff_it;// skip ' '
    char c1, c2;
    c1=*buff_it;
    ++buff_it;
    c2= *buff_it;
    if(c2 == '\n'){ edges_to_sort[i].n2_cost |= c1-'0'; }
    else {
      edges_to_sort[i].n2_cost |= (c1-'0')*10+ (c2-'0');
      ++buff_it; // to \n
    }
    ++buckets[(edges_to_sort[i].n2_cost & 0xFF)+1];
  }
  for(std::size_t i(1); i!=256; ++i) { buckets[i]+= buckets[i-1]; }
  for(std::size_t i(0); i!= nb_links; ++i) 
    { *(edges_out+((buckets[edges_to_sort[i].n2_cost & 0xFF])++))= edges_to_sort[i];}
}

//  https://en.wikipedia.org/wiki/Disjoint-set_data_structure
template<typename V>
struct disjoint_sets{
  typedef std::pair<V, std::size_t> parent_rank_t;
  std::unordered_map<V,parent_rank_t> data;

  void make_set(V const& v)
  { data[v]=std::make_pair(v, 1); }

  V find_set(V const& v)  {
    V & p(data[v].first);
    if(p != v) {p= find_set(p);}
    return p;
  }

  void link(V const& v1, V const& v2) {
    V root1(find_set(v1)), root2(find_set(v2));
    if(root1 == root2) { return; }
    parent_rank_t & p1(data[root1]);
    parent_rank_t & p2(data[root2]);
    if(p1.second < p2.second) { p1.first= root2; }
    else if (p1.second > p2.second) {p2.first= root1; }
    else {
      p2.first= root1; 
      ++p1.second;
    }
  }
};

int main(int argc, char* argv[]) {
  // these are not needed in fact, it's 2012 already !
  std::size_t nb_cities, nb_links;
// EDIT: OK you want to play by C rules, I'll bite ! :)
// must use std::strstream as std::istringstream makes a copy :(
  const std::size_t max_nb_chars_city_name(8), max_nb_chars_cost(2);
// 8 chars for city names ?
// if ASCII, I can use std::int64_t !
  typedef std::chrono::high_resolution_clock clock_t;
  typedef std::chrono::milliseconds milliseconds_t;
  std::chrono::time_point<clock_t> const start(clock_t::now());
  std::cin >> nb_cities >> nb_links;

  const std::size_t buff_size(nb_links*((max_nb_chars_city_name+1)*2
                                        + max_nb_chars_cost+1)+1);

  char* buff= new char[buff_size];
  std::cin.read(buff, buff_size);
  std::size_t actual_size(std::cin.gcount());
  std::vector<edge> edges_todo(nb_links);
  //skip \n
  read_edges(buff+1, actual_size, edges_todo.begin(), nb_links);
  std::chrono::time_point<clock_t> const parsed(clock_t::now());
  std::cerr<<"data file parsed in "<<std::chrono::duration_cast<milliseconds_t>(parsed-start).count()<<" ms."<<std::endl;

  delete [] buff;
  make_names_unique();
  std::chrono::time_point<clock_t> const unique(clock_t::now());
  std::cerr<<"city_names processed in "<<std::chrono::duration_cast<milliseconds_t>(unique-parsed).count()<<" ms."<<std::endl;

  disjoint_sets<int64_t> trees;
  std::for_each(unique_names.begin(), unique_names.end(), [&trees](int64_t const c){trees.make_set(c);});
  std::size_t total(0);
  // start at 1 because we need nb-1 merges to have one last set
  for(std::size_t merges_done(1), i(0); merges_done != unique_names.size(); ++i) {
    edge const& t(edges_todo[i]);
    auto s1(trees.find_set(t.n1)), s2(trees.find_set(t.n2_cost & ~0xFF));
    if(s1 != s2) {
      trees.link(s1, s2);
      total+= t.n2_cost & 0xFF;
      ++merges_done;
    }
  }
  std::cout << total << std::endl;
  std::chrono::time_point<clock_t> const finished(clock_t::now());
  std::cerr<<"minimum spanning tree computed in "<<std::chrono::duration_cast<milliseconds_t>(finished-unique).count()<<" ms."<<std::endl;
  return 0;
}

iptv_ugly_hack_int_names.cxx

#include <string>
#include <iostream>
#include <strstream>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <list>
#include <iterator>
#include <algorithm>
#include <queue>
#include <chrono>

#include <cstdint>

// g++-snapshot -std=c++11 my_third_take.cxx -o my_third_take -O4 -march=native
/*
for storing edges a  C++11 priority_queue
Cheating : exploiting 8 chars names and assuming ASCII (even 8 bits extensions)
for disjoint sets https://en.wikipedia.org/wiki/Disjoint-set_data_structure
*/

std::unordered_set<int64_t> city_names;

// undirected ->could reorder nodes
struct edge {
  // as priority queue returns the max elts, we simply use > for operator< to get the min elt
  bool operator<(edge const& o)const{ return cost > o.cost;}
  union city_t {
    int64_t as_int;
    char as_chars[8] ;
};
  city_t n1;
  city_t n2;
  std::size_t cost;
};
// FAST and FURIOUS HACK: *very fragile* do no use in production, only to show off :)
template<typename IStream > IStream& operator>>(IStream& is, edge& e){
  std::string tmp;
  bool ok(false);
  e.n1.as_int= e.n2.as_int= 0;
  if(is.get(e.n1.as_chars, 8, ' ')) {
    is.get();// skip ' '
    if(is.get(e.n2.as_chars, 8, ' ')) {
      is.get();// skip ' '
      char c1,c2;
      if(is.get(c1)){
        if(is.get(c2)){
          if (c2=='\n') { e.cost= c1-'0'; }
          else {
            e.cost= (c1-'0')*10+ (c2-'0');
            is.get();// skip '\n'
          }
          ok= true;
          city_names.insert(e.n1.as_int);
          city_names.insert(e.n2.as_int);
        }
      }
    }
  }
  if(!ok){ is.setstate(std::ios::failbit);}
  return is;
}

//  https://en.wikipedia.org/wiki/Disjoint-set_data_structure
template<typename V>
struct disjoint_sets{
  typedef std::pair<V, std::size_t> parent_rank_t;
  std::unordered_map<V,parent_rank_t> data;

  void make_set(V const& v)
  { data[v]=std::make_pair(v, 1); }

  V find_set(V const& v)  {
    V & p(data[v].first);
    if(p != v) {p= find_set(p);}
    return p;
  }

  void link(V const& v1, V const& v2) {
    V root1(find_set(v1)), root2(find_set(v2));
    if(root1 == root2) { return; }
    parent_rank_t & p1(data[root1]);
    parent_rank_t & p2(data[root2]);
    if(p1.second < p2.second) { p1.first= root2; }
    else if (p1.second > p2.second) {p2.first= root1; }
    else {
      p2.first= root1; 
      ++p1.second;
    }
  }
};


int main(int argc, char* argv[]) {
  // these are not needed in fact, it's 2012 already !
  std::size_t nb_cities, nb_links;
// EDIT: OK you want to pay by C rules, I'll bite ! :)
// must use std::strstream as std::istringstream makes a copy :(
const std::size_t max_nb_chars_city_name(8), max_nb_chars_cost(2);
// 8 chars for city names ?
// if ASCII, I can use std::int64_t !
  typedef std::chrono::high_resolution_clock clock_t;
  typedef std::chrono::milliseconds milliseconds_t;
  std::chrono::time_point<clock_t> const start(clock_t::now());
  std::cin >> nb_cities >> nb_links;
  const std::size_t buff_size(nb_links*((max_nb_chars_city_name+1)*2
                                        + max_nb_chars_cost+1)+1);

  char* buff= new char[buff_size];
  std::cin.read(buff, buff_size);
  std::istrstream buff_stream(buff);
        buff_stream.get();// skip '\n'
  std::istream_iterator<edge> b(buff_stream), end;
  std::priority_queue<edge> edges_todo;
  std::for_each(b, end 
                ,[&edges_todo](edge const& ed){edges_todo.push(ed);});
  delete [] buff;
  std::chrono::time_point<clock_t> const parsed(clock_t::now());
  std::cerr<<"data file parsed in "<<std::chrono::duration_cast<milliseconds_t>(parsed-start).count()<<" ms."<<std::endl;
  disjoint_sets<int64_t> trees;
  std::for_each(city_names.begin(), city_names.end(), [&trees](int64_t const c){trees.make_set(c);});
  std::size_t total(0);
  // start at 1 because we need nb-1 merges to have one last set
  for(std::size_t merges_done(1); merges_done != city_names.size()
        ; edges_todo.pop()) {
    edge const& t(edges_todo.top());
    auto s1(trees.find_set(t.n1.as_int)), s2(trees.find_set(t.n2.as_int));
    if(s1 != s2) {
      trees.link(s1, s2);
      total+= t.cost;
      ++merges_done;
    }
  }
  std::cout << total << std::endl;
  std::chrono::time_point<clock_t> const finished(clock_t::now());
  std::cerr<<"minimum spanning tree computed in "<<std::chrono::duration_cast<milliseconds_t>(finished-parsed).count()<<" ms."<<std::endl;
  return 0;
}

iptv_wikipedia.cxx

#include <string>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <list>
#include <iterator>
#include <algorithm>
#include <queue>
#include <chrono>

// g++-snapshot -std=c++11 my_third_take.cxx -o my_third_take -O4 -march=native
/*
for storing edges a  C++11 priority_queue
for efficient nodes compares, we intern the city names and use pointers to the interned canonical strings.
for disjoint sets https://en.wikipedia.org/wiki/Disjoint-set_data_structure
*/
// for interning
std::unordered_set<std::string> city_names;

// undirected ->could reorder nodes
struct edge {
  // as priority queue returns the max elts, we simply use > for operator< to get the min elt
  bool operator<(edge const& o)const{ return cost > o.cost;}
  std::string const* n1;
  std::string const* n2;
  std::size_t cost;
};

template<typename IStream > IStream& operator>>(IStream& is, edge& e){
  std::string tmp;
  bool ok(false);
  if(is >> tmp) {
    e.n1= &(*(city_names.insert(tmp).first));
    if(is >> tmp) {
      e.n2= &((*city_names.insert(tmp).first));
      if(is >> e.cost){
        ok= true;
      }
    }
  }
  if(!ok){ is.setstate(std::ios::failbit);}
  return is;
}

//  https://en.wikipedia.org/wiki/Disjoint-set_data_structure
template<typename V>
struct disjoint_sets{
  typedef std::pair<V, std::size_t> parent_rank_t;
  std::unordered_map<V,parent_rank_t> data;

  void make_set(V const& v)
  { data[v]=std::make_pair(v, 1); }

  V find_set(V const& v)  {
    V & p(data[v].first);
    if(p != v) {p= find_set(p);}
    return p;
  }

  void link(V const& v1, V const& v2) {
    V root1(find_set(v1)), root2(find_set(v2));
    if(root1 == root2) { return; }
    parent_rank_t & p1(data[root1]);
    parent_rank_t & p2(data[root2]);
    if(p1.second < p2.second) { p1.first= root2; }
    else if (p1.second > p2.second) {p2.first= root1; }
    else {
      p2.first= root1; 
      ++p1.second;
    }
  }
};

int main(int argc, char* argv[]) {
  // these are not needed in fact, it's 2012 already !
  std::size_t nb_cities, nb_links;
  typedef std::chrono::high_resolution_clock clock_t;
  typedef std::chrono::milliseconds milliseconds_t;
  std::chrono::time_point<clock_t> const start(clock_t::now());
  std::cin >> nb_cities >> nb_links;

  std::istream_iterator<edge> b(std::cin), end;
  std::priority_queue<edge> edges_todo;
  std::for_each(b, end 
                ,[&edges_todo](edge const& ed){edges_todo.push(ed);});
  std::chrono::time_point<clock_t> const parsed(clock_t::now());
  std::cerr<<"data file parsed in "<<std::chrono::duration_cast<milliseconds_t>(parsed-start).count()<<" ms."<<std::endl;
  disjoint_sets<std::string const*> trees;
  std::for_each(city_names.begin(), city_names.end(), [&trees](std::string const& c){trees.make_set(&c);});
  std::size_t total(0);
  // start at 1 because we need nb-1 merges to have one last set
  for(std::size_t merges_done(1); merges_done != city_names.size()
        ; edges_todo.pop()) {
    edge const& t(edges_todo.top());
    auto s1(trees.find_set(t.n1)), s2(trees.find_set(t.n2));
    if(s1 != s2) {
      trees.link(s1, s2);
      total+= t.cost;
      ++merges_done;
    }
  }
  std::cout << total << std::endl;
  std::chrono::time_point<clock_t> const finished(clock_t::now());
  std::cerr<<"minimum spanning tree computed in "<<std::chrono::duration_cast<milliseconds_t>(finished-parsed).count()<<" ms."<<std::endl;
  return 0;
}