cafelier@SRM

Facebook Hacker Cup 2012 R2 Monopoly

FHC | 21:50 |

• マージするたびに、「この会社を高さhで作った場合の社長直属の部下の最小数は何人？」という h \mapsto d の表を計算。
• N-1回のマージで、高さは高々（高さは高々！）Nにしかならないので表のサイズはNまでなので、
• O(N^2) 時間あれば終わる。
• この h \mapsto d は単調減少だから確か何か工夫するとオーダー落とせるんだよなあ蟻本蟻本…
• と思っている途中で制約を見たら N≦3万 でした。
• 6分なら9億が20ケースは時間足りますね。
• しかも実際の入力データめちゃくちゃ弱くて一瞬で本当に終わってしまった。

typedef tuple<int, int> merger;

template<typename T>
struct UnionFind
{
   vector<int> uf, sz;
   vector<T> info;
   int nc;

   UnionFind(int N, const T& ini): uf(N), sz(N,1), nc(N), info(N, ini)
      { for(int i=0; i<N; ++i) uf[i] = i; }
   int size()
      { return nc; }
   int Find(int a)
      { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
   T& Info(int a)
      { return info[Find(a)]; }
   template<typename F>
   bool Union(int a, int b, F info_merger)
      {
         a = Find(a);
         b = Find(b);
         if( a != b )
         {
            if( sz[a] >= sz[b] ) swap(a, b);
            uf[a] = b;
            sz[b] += sz[a];
            info_merger(info[b], info[a]);
            --nc;
         }
         return (a!=b);
      }
};

int solve(const vector<merger>& ms, int N, int D)
{
   typedef vector<int> HD;
   static const int INF = 0x3fffffff;

   UnionFind<HD> uf(N, HD({INF,0}));
   for(auto m : ms) {
      uf.Union(get<0>(m), get<1>(m), [&](HD& a, HD b){
         int aMinD = INF;
         int bMinD = INF;
         HD c(max(a.size(),b.size())+1, INF);
         for(int h=1; h<c.size(); ++h) {
            int c1 = aMinD>=INF || h>=b.size() ? INF : b[h]+1;
            int c2 = bMinD>=INF || h>=a.size() ? INF : a[h]+1;
            int c3 = aMinD>=INF || h-1>=b.size() || b[h-1]>=INF ? INF : min(aMinD, b[h-1])+1;
            int c4 = bMinD>=INF || h-1>=a.size() || a[h-1]>=INF ? INF : min(bMinD, a[h-1])+1;
            c[h] = min({c1, c2, c3, c4, INF});
            if(c[h]>D) c[h] = INF;
            if(h<a.size()) aMinD = min(aMinD, a[h]);
            if(h<b.size()) bMinD = min(bMinD, b[h]);
         }
         a = c;
      });
   }
   HD& hd = uf.Info(0);
   for(int h=0; h<hd.size(); ++h)
      if( hd[h] <= D )
         return h;
   return -1;
}

int main()
{
   int T; cin >> T;
   for(int C=1; C<=T; ++C)
   {
      int N, D; cin >> N >> D;
      vector<merger> ms(N-1);
      for(auto& m : ms) {
         cin >> get<0>(m) >> get<1>(m);
         -- get<0>(m);
         -- get<1>(m);
      }
      cout << "Case #" << C << ": " << solve(ms, N, D) << endl;
   }
}