记录编号	216930	评测结果	AAAAAAAAAA
题目名称	[SCOI 2012] 喵星球上的点名	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.558 s
提交时间	2016-01-01 16:30:23	内存使用	5.12 MiB

#include<cstdio>
#include<map>
#include<vector>
int EPX,n,m,len,x,name[210000],t1[210000],t2[210000],ans[210000];
inline void in(int &TEMP)
{
	for(TEMP=getchar();TEMP<48||TEMP>57;TEMP=getchar());
	TEMP^=48;
	for(EPX=getchar();EPX<58&&EPX>47;EPX=getchar())
		TEMP=(TEMP<<3)+(TEMP<<1)+(EPX^48);
}
struct node
{
	std::map<int,node*>mp;
	std::vector<int>v;
	int num,ans,flag;
	node *fail;
	node()
	{
		fail=NULL;
		num=ans=flag=0;
	}
}*root,*p,*tmp,*id[210000],*q[210000];
void build()
{
	in(n),in(m);
	for(int i=1;i<=n;++i)
	{
		in(t2[i]);
		t2[i]+=t1[i];
		for(int j=t1[i];j<t2[i];++j)
		    in(name[j]);
		in(t1[i+1]);
		t1[i+1]+=t2[i];
		for(int j=t2[i];j<t1[i+1];++j)
		    in(name[j]);
	}
	root=new node;
	for(int i=1;i<=m;++i)
	{
		in(len);
		p=root;
		while(len--)
		{
			in(x);
			if(!p->mp[x])
			{
				p->v.push_back(x);
			    p->mp[x]=new node;
			}
			p=p->mp[x];
		}
		++p->num;
		id[i]=p;
	}
}
int l,r;
void get_fail()
{
	q[0]=root;
	while(l<=r)
	{
		p=q[l++];
		for(int i=0,lim=p->v.size();i<lim;++i)
		{
			x=p->v[i];
			tmp=p->fail;
			while(tmp&&!tmp->mp[x])
			    tmp=tmp->fail;
			if(tmp)
				p->mp[x]->fail=tmp->mp[x];
			else
			    p->mp[x]->fail=root;
			q[++r]=p->mp[x];
		}
	}
}
void solve()
{
	for(int i=1;i<=n;++i)
	{
		p=root;
		for(int j=t1[i];j<t2[i];++j)
		{
			while(p&&!p->mp[name[j]])
				p=p->fail;
			if(p)
			    p=p->mp[name[j]];
			else
			    p=root;
			tmp=p;
			while(tmp)
			{
				if(tmp->flag!=i)
				{
					tmp->flag=i;
					ans[i]+=tmp->num;
					++tmp->ans;
				}
				tmp=tmp->fail;
			}
		}
		p=root;
		for(int j=t2[i];j<t1[i+1];++j)
		{
			while(p&&!p->mp[name[j]])
				p=p->fail;
			if(p)
			    p=p->mp[name[j]];
			else
			    p=root;
			tmp=p;
			while(tmp)
			{
				if(tmp->flag!=i)
				{
					tmp->flag=i;
					ans[i]+=tmp->num;
					++tmp->ans;
				}
				tmp=tmp->fail;
			}
		}
	}
	for(int i=1;i<=m;++i)
	    printf("%d\n",id[i]->ans);
	for(int i=1;i<=n;++i)
	    printf("%d ",ans[i]);
}
int main()
{
	freopen("wtfname.in","r",stdin);
	freopen("wtfname.out","w",stdout);
	build();
	get_fail();
	solve();
	//while(1);
}