DFS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define not !
#define and &&
#define or ||
#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)
#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, ~0) printf("%d%c", getbit(x, i), i ? 9 : 10); }
#define SWAP(a, b) { typeof(a) tmp = a; a = b; b = tmp; }
typedef long long int ll;
#define r() fast_read()
bool is_digit(const char c) {
return c >= 48 and c <= 57;
}
ll my_pow(int base, int exponent) {
return exponent ? my_pow(base, exponent - 1) * base : 1;
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (not is_digit(c)) {
if (c == '-') sign = ~0;
c = getchar();
}
while (is_digit(c)) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
void swap(void* a, void* b, size_t size) {
char *p = (char*) a, *q = (char*) b;
rep(i, 0, size) *p ^= *q, *q ^= *p, *p++ ^= *q++;
}
void bubble_sort(void* base,
size_t num,
size_t size,
int (*compar) (const void*, const void*)) {
rep(i, 0, num - 1) {
bool exchange = 0;
rep(j, 0, num - 1 - i) {
if (compar(base + j * size, base + (j + 1) * size) > 0) {
swap(base + j * size, base + (j + 1) * size, size);
exchange = 1;
}
}
if (not exchange) break;
}
}
#define MAX_N 100010
int head[MAX_N], edge_cnt;
typedef struct Edge Edge;
struct Edge {
int to, nxt;
} edges[MAX_N];
void addEdge(int u, int v) {
edges[++edge_cnt] = (Edge) {v, head[u]};
head[u] = edge_cnt;
}
void print_graph(const int n) {
rep(u, 0, n) {
printf("Vertex: %d -->", u);
for (int e = head[u]; e; e = edges[e].nxt)
printf("[%d]\t", edges[e].to);
putchar(10);
}
}
int n, cnt;
double p, r;
void DFS(int root, int depth, int* max_depth) {
if (depth > *max_depth) *max_depth = depth, cnt = 1;
else if (depth == *max_depth) ++cnt;
for (int e = head[root]; e; e = edges[e].nxt)
DFS(edges[e].to, depth + 1, max_depth);
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
n = r();
scanf("%lf%lf", &p, &r);
int parent, root;
rep(u, 0, n) {
parent = r();
if (parent == -1) root = u;
else addEdge(parent, u);
}
int max_depth = -1;
DFS(root, 0, &max_depth);
printf("%.2lf %d\n", p * pow(1 + r / 100, max_depth), cnt);
// fclose(stdin);
return ~~(0 ^ 0);
}
BFS Algorithm
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, parent, root_id;
double p, r;
pair<double, int> bfs(vector<vector<int>>& g) {
queue<int> q{{root_id}};
int num = 0, depth = 0;
while (not q.empty()) {
size_t sz = q.size();
num = sz;
while (sz--) {
const auto cur = q.front(); q.pop();
for (const auto& child : g[cur])
q.emplace(child);
}
++depth;
}
double price = p;
for (int i = 0; i < depth - 1; ++i)
price *= 1 + r / 100.0;
return {price, num};
}
int main(void) {
scanf("%d %lf %lf", &n, &p, &r);
vector<vector<int>> g(n);
for (int i = 0; i < n; ++i) {
cin >> parent;
if (parent == -1) {
root_id = i;
continue;
}
g[parent].emplace_back(i);
}
const auto [price, num] = bfs(g);
printf("%.2lf %d", price, num);
}