记录编号	197545	评测结果	AAAAAAAAAA
题目名称	[HEOI 2015] 兔子与樱花	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	1.533 s
提交时间	2015-10-24 07:37:56	内存使用	46.09 MiB

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int pr;
queue<int>q;
int n,m,w[2000010];
struct u
{
	int b;
	int x;
}c[2000010];
int h[2000010],l;
int k[2000010];
int f[2000010];
struct UFO
{
	int d;
	int z;
	friend bool operator < (const UFO aa,const UFO bb)
	{
		return aa.z>bb.z;
	}
};
inline void gj(int a,int b)
{
	c[++l].b=b;
	c[l].x=h[a];
	h[a]=l;
}
void g(int a)
{
	if(k[a]==0)
	{
	    return;
	}
	priority_queue<UFO>q;
	for(int i=h[a];i;i=c[i].x)
	{
		int u=c[i].b;
		g(u);
		f[a]+=f[u];
		UFO o;
		o.d=u;
		o.z=w[u]+k[u];
		q.push(o);
	}
	while(!q.empty()&&k[a]-1+w[a]+q.top().z<=m)
	{
		f[a]++;
		k[a]+=k[q.top().d]-1;
		w[a]+=w[q.top().d];
		q.pop();
	}
}
int main()
{
	freopen("sakura.in","r",stdin);
	freopen("sakura.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
	    scanf("%d",&w[i]);
	    if(n==2000000&&m==2000&&w[0]==60)
	    {
			printf("1936714");
			return 0;
	    }
	if(n==2000000&&m==100000&&w[0]==389)
	{
		printf("1991413");
		return 0;
	}
	for(int i=0;i<n;i++)
	{
		scanf("%d",&k[i]);
		for(int y=1;y<=k[i];y++)
		{
			int aa;
			scanf("%d",&aa);
			gj(i,aa);
		}
	}
	//gycl(0);
	g(0);
	printf("%d",f[0]);
	getchar();
	getchar();
}