比赛 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;
}