This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
ノードは自分の子に対してnewsを伝えることが出来る．1人の人は1人にしか伝えることが出来ず，同時に複数人に伝える事はできない．最終的に全ての人に伝わえるまで何ステップかかるか
上の画像の赤いノードについて考える．下の子については既にそのノード以下に全て伝えるには何ステップかかるか，という値が分かっていて，左から$2, 3, 4$であったとする．この時赤いノードはどのノードに情報を伝えるかの順番を選ぶことができる．子ノードに伝えてから子ノードは情報の伝搬を始めるので，最小を求めるには値の大きい順に伝えていけば良い．子ノードの値を降順ソートし，その値$+$index$+1$(順番に伝える)の$max$が赤いノード以下に全て伝えるステップ数となる．これを再帰的に全てのノードについて行った．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
typedef pair < P , int > PI ;
vector < int > g [ 55 ];
int dfs ( int i ) {
if ( g [ i ]. size () == 0 ) return 0 ;
vector < int > v ;
rep ( j , g [ i ]. size ()) {
v . push_back ( dfs ( g [ i ][ j ]));
}
sort ( v . begin (), v . end (), greater < int > ());
int ret = 0 ;
rep ( i , v . size ()) {
ret = max ( ret , v [ i ] + i + 1 );
}
return ret ;
}
class SpreadingNews {
public :
int minTime ( vector < int > supervisors ) {
int n = supervisors . size ();
rep ( i , 55 ) g [ i ]. clear ();
int root = - 1 ;
rep ( i , n ) {
if ( supervisors [ i ] == - 1 ) {
root = i ;
} else {
g [ supervisors [ i ]]. push_back ( i );
}
}
return dfs ( root );
}
};
