-
Notifications
You must be signed in to change notification settings - Fork 0
/
1090.cpp
68 lines (61 loc) · 1.18 KB
/
1090.cpp
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
62
63
64
65
66
67
68
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int main(int argc, char *argv[]) {
int N;
double P, r;
scanf("%d%lf%lf", &N, &P, &r);
r = 1.0 + r / 100;
vector<int> pre(N, 0);
for(int i = 0; i < N; ++i) {
scanf("%d", &pre[i]);
}
vector<int> root;
vector< vector<int> > v(N, vector<int>());
for(int i = 0; i < pre.size(); ++i) {
if(-1 == pre[i])
root.push_back(i);
else {
v[ pre[i] ].push_back(i);
}
}
int curNum = 0, curLen = 0, preNum = 0;
queue<int> q;
for(int i = 0; i < root.size(); ++i) {
q.push(root[i]);
curNum++;
}
preNum = curNum;
curNum = 0;
q.push(-2);
while(q.size() != 0) {
if(-2 == q.front() && q.size() == 1) {
q.pop();
break;
}
else if(-2 == q.front()) {
q.pop();
q.push(-2);
preNum = curNum;
curNum = 0;
++curLen;
continue;
}
int curIndex = q.front();
q.pop();
for(int i = 0; i < v[curIndex].size(); ++i) {
q.push(v[curIndex][i]);
curNum++;
}
// curNum += v[curIndex].size();
}
double result = P;
for(int i = 0; i < curLen; ++i) {
result *= r;
}
// cout << curLen << " " << preNum << endl;
printf("%.2f %d\n", result, preNum);
return 0;
}