记录编号	394843	评测结果	AAAAAAAAAA
题目名称	[SCOI 2012] 喵星球上的点名	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.601 s
提交时间	2017-04-14 18:04:45	内存使用	16.41 MiB

#include<cstdio>
#include<queue>
#include<map>
using namespace std;
const int N=4e5+10;
int n,m,top,len[N],par[N];
map<int,int> go[N];
int New(int L){len[++top]=L;return top;}
int extend(int last,int w){
	int p=last,np=New(len[p]+1);
	while (p&&!go[p][w]) go[p][w]=np,p=par[p];
	if (!p) par[np]=1;
	else{
		int q=go[p][w];
		if (len[q]==len[p]+1) par[np]=q;
		else{
			int nq=New(len[p]+1);
			go[nq]=go[q];
			par[nq]=par[q];
			par[np]=par[q]=nq;
			while (p&&go[p][w]==q) go[p][w]=nq,p=par[p];
		}
	}
	return np;
}
int vis[N],s[N],cnt[N];
void paint(int x,int C){
	if (!x||vis[x]==C) return;
	vis[x]=C;s[x]++;
	paint(par[x],C);
}
int sum(int x,int C){
	if (!x||vis[x]==C) return 0;
	vis[x]=C;
	return cnt[x]+sum(par[x],C);
}
const int M=5e4+10;
vector<int> a[M],b[M];
int main()
{
	freopen("wtfname.in","r",stdin);
	freopen("wtfname.out","w",stdout);
	scanf("%d%d",&n,&m);
	New(0);
	for (int id=1;id<=n;id++){
		int len,w;
		scanf("%d",&len);
		for (int i=1,last=1;i<=len;i++){
			scanf("%d",&w);
			a[id].push_back(w);
			last=extend(last,w);
		}
		scanf("%d",&len);
		for (int i=1,last=1;i<=len;i++){
			scanf("%d",&w);
			b[id].push_back(w);
			last=extend(last,w);
		}
	}
	for (int id=1;id<=n;id++){
		for (int i=0,last=1;i<a[id].size();i++){
			last=go[last][a[id][i]];
			paint(last,id);
		}
		for (int i=0,last=1;i<b[id].size();i++){
			last=go[last][b[id][i]];
			paint(last,id);
		}
	}
	for (int i=1;i<=m;i++){
		int len,w,last=1;
		scanf("%d",&len);
		for (int i=1;i<=len;i++){
			scanf("%d",&w);
			last=go[last][w];
		}
		printf("%d\n",s[last]);
		cnt[last]++;
	}
	for (int id=1;id<=n;id++){
		int ans=0;
		for (int i=0,last=1;i<a[id].size();i++){
			last=go[last][a[id][i]];
			ans+=sum(last,n+id);
		}
		for (int i=0,last=1;i<b[id].size();i++){
			last=go[last][b[id][i]];
			ans+=sum(last,n+id);
		}
		printf("%d ",ans);
	}
	puts("");
	return 0;
}