my model
04 December 2014
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 # include <iomanip>
5 #define N 100010
6 using namespace std;
7 int Tree[N];
8 int num[N];
9 int f[N];
10 int findRoot(int x){
11 if(Tree[x]==x) return x;
12 int fx=Tree[x];
13 Tree[x]=findRoot(Tree[x]);
14 f[x]=f[fx]+f[x];
15 return Tree[x];
16 }
17 void merge(int x,int y) {
18 int fx = findRoot(x);
19 int fy = findRoot(y);
20 if(fx==fy) {
21
22 }else {
23 Tree[fx] = fy;
24 f[fx] = (f[y] - f[x] + 1);
25 }
26 }
27 int main(){
28 int n,s;
29 double p,r;
30 while(~scanf("%d%lf%lf",&n,&p,&r)){
31 for(int i=0;i<n;i++){
32 Tree[i]=i;
33 f[i]=0;
34 }
35 for(int i=0;i<n;i++){
36 scanf("%d",&s);
37 if(s==-1) continue;
38 merge(i,s);
39 }
40
41 int sameN=0;
42 int deep=0;
43 for(int i=0;i<n;i++){
44 findRoot(i);
45 //printf("%d: %d\n",i,f[i]);
46 if(f[i]>deep){
47 deep=f[i];
48 sameN=1;
49 }else if(f[i]==deep){
50 sameN++;
51
52 }
53 }
54 double ansPrice=p;
55 for(int i=0;i<deep;i++){
56 ansPrice=ansPrice*(1+r/100);
57 }
58 printf("%.2lf %d",ansPrice,sameN);
59
60 }
61 return 0;
62 }
blog comments powered by Disqus