【PAT甲级】1090 Highest Price in Supply Chain (25 分)

时间:2023-03-09 16:02:29
【PAT甲级】1090 Highest Price in Supply Chain (25 分)

题意:

输入一个正整数N(<=1e5),和两个小数r和f,表示树的结点总数和商品的原价以及每向下一层价格升高的幅度。下一行输入N个结点的父结点,-1表示为根节点。输出最深的叶子结点处购买商品的价格以及有几个深度最深的结点。

AAAAAccepted code:

 #define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[];
vector<int>v[];
int mx;
int ans[];
void dfs(int x,int storey){
mx=max(mx,storey);
ans[x]=storey;
for(auto it:v[x])
dfs(it,storey+);
}
int main(){
int n;
int root=;
double p,r;
cin>>n>>p>>r;
for(int i=;i<=n;++i){
cin>>a[i];
if(a[i]==-)
root=i-;
else
v[a[i]].push_back(i-);
}
dfs(root,);
int num=;
for(int i=;i<n;++i)
if(ans[i]==mx)
++num;
double sum=p*pow(+r/100.0,mx);
printf("%.2lf %d",sum,num);
return ;
}