SRM316Div2

250

class HiddenMessage {
public:
  string getMessage(string text) {
    string s;
    istringstream iss(text);
    for(string t; iss >> t; s += t[0]);
    return s;
  }
}; 

500

class InboxCleanup {
public:
  int fewestClicks(string msg, int l, int h) {
    int r = 1 << 24;
    for(int lim=l; lim<=h; ++lim){
      int sum = 0;
      for(int i=0; i<msg.size(); i+=lim){
        string p = msg.substr(i, lim);
        int d = count(p.begin(), p.end(), 'D');
        if(d)sum += min(d + 1, (int)p.size()-d+2);
        if(i)++sum;
      }
      r = min(r, sum);
    }
    return r;
  }
}; 

1000

const int N = 50 + 1;
vector<int> next[N];

int rec(int v)
{ 
  int mx = 0;
  vector<int> cost;
  for(int i=0; i<next[v].size(); ++i){
    cost.push_back( rec( next[v][i] ) );
  }  
  sort(cost.begin(), cost.end());
  reverse(cost.begin(), cost.end());
  for(int i=0; i<cost.size(); ++i){
    mx = max(mx, cost[i] + i + 1);
  }
  return mx;
}

class SpreadingNews {
public:
  int minTime(vector <int> s) {
    fill(next, next + s.size(), vector<int>());
    for(int i=0; i<s.size(); ++i){
      if(0 <= s[i])next[s[i]].push_back(i);
    }    
    return rec(0);
  }
};