5pts求助
查看原帖
5pts求助
697421
Quenna楼主2023/7/3 10:36
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+1;
int n,k;
int f[MAXN];
vector<int> dot[MAXN];
long long kkksc03;
queue<int>edge_1,edge_2;
bool d[MAXN];
inline int ksk(int vc){
	int i=1;
	while(vc/=10){
		i++;
	} 
	return i;
}
inline void bfs(int x){
	edge_1.push(x);
	edge_2.push(f[x]);
	memset(d,0,sizeof(d));
	while(!edge_1.empty()){
		for(int i=0;i<edge_1.size();i++){
			if(!d[edge_1.front()]){
				d[edge_1.front()]=1;
				kkksc03+=edge_2.front();
				for(int j=0;j<dot[edge_1.front()].size();j++){
					edge_1.push(dot[edge_1.front()][j]);
					edge_2.push(edge_2.front()*pow(10,ksk(f[dot[edge_1.front()][j]]))+f[dot[edge_1.front()][j]]);
				}
			}
			edge_1.pop();
			edge_2.pop();
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); 
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>f[i];
	for(int i=1;i<n;i++){
		cin>>k;
		dot[k].push_back(i+1);
		dot[i+1].push_back(k);
	}
	for(int i=1;i<=n;i++){
		bfs(i);
	}
	cout<<kkksc03%998244353;
}

BFS,过了样例(全部),但TLE了

2023/7/3 10:36
加载中...