比赛 |
20241127 |
评测结果 |
AAAAAWWAAA |
题目名称 |
魔法药水 |
最终得分 |
80 |
用户昵称 |
flyfree |
运行时间 |
2.885 s |
代码语言 |
C++ |
内存使用 |
472.02 MiB |
提交时间 |
2024-11-27 10:02:39 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1010
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
ll idx,n,id;
ll val[MAXN*MAXN*20],f[MAXN*MAXN*20],cur[MAXN*MAXN*20];
queue<ll> q;
vector <ll> vec[MAXN*MAXN*20];
void build(ll x,ll y){
vec[x].push_back(y);
// cur[x]=vec[x].size();
}
void dfs(ll now){
// ins[now]=1;
if(cur[now]==vec[now].size()-1)return;
for(ll i=cur[now]+1;i<vec[now].size();i=cur[now]+1){
cur[now]=i;
ll y=vec[now][i];
dfs(y);
if(now<=n){
if(val[y]<val[now]){
val[now]=val[y];
f[now]=f[y];
}else if(val[y]==val[now]){
f[now]+=f[y];
}
}else{
val[now]+=val[y];
f[now]*=f[y];
}
}
// if(now<=n)cout<<now<<" "<<val[now]<<" "<<f[now]<<endl;
}
int main(){
freopen("msyrup.in","r",stdin);
freopen("msyrup.out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
val[i]=read();
f[i]=1,cur[i]=-1;
}
ll a,b,c;
id=n;
while(cin>>a>>b>>c){
a++,b++,c++;
build(c,++id),build(id,a),build(id,b);
cur[id]=-1,f[id]=1,val[id]=0;
}
dfs(1);
cout<<val[1]<<" "<<f[1]<<endl;
// for(int i=0;i<vec[1].size();i++){
// ll y=vec[1][i];
// if(val[y]==val[1])cout<<"1: "<<y<<" "<<val[y]<<" "<<f[y]<<endl;
// }
return 0;
}