求助 MLE qwq
查看原帖
求助 MLE qwq
578932
AlphaGuo楼主2022/11/3 00:51
#include<bits/stdc++.h>

using namespace std;

const int N=2*1e6+1;

vector<int>G[N];
int n,m,ans,k[N],c[N];

struct node{
	int id;
	bool friend operator<(node a,node b){return c[a.id]+k[a.id]>c[b.id]+k[b.id];}
};

void dfs(int now,int fa){
	priority_queue<node>q;
	for(int x:G[now])
		if(x!=fa)dfs(x,now),q.push({x});
	while(!q.empty()&&c[now]+k[now]+c[q.top().id]+k[q.top().id]-1<=m)c[now]+=c[q.top().id],k[now]+=k[q.top().id]-1,ans++,q.pop();
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++){
		cin>>k[i];
		for(int j=1,tem;j<=k[i];j++)cin>>tem,G[i].emplace_back(tem+1),G[tem+1].emplace_back(i);
	}
	dfs(1,0);return cout<<ans<<endl,0;
}
2022/11/3 00:51
加载中...