记录编号	40849	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 信使问题a	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	4.035 s
提交时间	2012-07-19 14:43:02	内存使用	194.13 MiB

#include <cstdio>
#include <cstring>

#define I_F "postmana.in"
#define O_F "postmana.out"

const int MAXn=10000;
const long MAXl=200+1;

struct edge
{
	int x;
	edge *next;
};
struct trie
{
	char c;
	int flag;
	trie *father, *fail;
	trie *p[26];
};
struct que
{
	trie *x;
	que *next;
};

int n, m;
char ms[MAXn][100*MAXl], ns[MAXn][MAXl];
short w[MAXn];
long ws[MAXn]={0};
int h[MAXn+1], o[MAXn];
long ans;
bool f[MAXn];
edge *mapn[MAXn]={NULL}, *mapm[MAXn]={NULL};
trie *root;

template<typename Any>
inline void Swap(Any&, Any&);
void Input();
void Trie_add(const char*, const int&);
void Trie_getfail();
void Prework();
void Match();
void Getheap();
void Search();
void Output();

int main()
{
	Input();
	Prework();
	Match();
	Getheap();
	Search();
	Output();
	return 0;
}

template<typename Any>
inline void Swap(Any &a, Any &b)
{
	Any t=a;
	a=b;
	b=t;
}

void Input()
{
	freopen(I_F,"r",stdin);
	scanf("%d%d",&m,&n);
	for (int i=0; i<m; ++i)
		scanf("%s",ms[i]);
	for (int i=0; i<n; ++i)
		scanf("%hd %s\n",&w[i],ns[i]);
}

void Trie_add(const char *s, const int &x)
{
	short l=strlen(s), t;
	trie *p=root;
	for (short i=0; i<l; ++i)
	{
		t=s[i]-'a';
		if (p->p[t]==NULL)
		{
			p->p[t]=new trie;
			p->p[t]->c=s[i];
			p->p[t]->father=p;
			p->p[t]->fail=NULL;
			p->p[t]->flag=-1;
			for (short j=0; j<26; ++j)
				p->p[t]->p[j]=NULL;
		}
		p=p->p[t];
		if (i==l-1)
			p->flag=x;
	}
}

void Prework()
{
	root=new trie;
	root->c=0;
	root->flag=-1;
	root->father=root->fail=NULL;
	for (short i=0; i<26; ++i)
		root->p[i]=NULL;
	for (int i=0; i<n; ++i)
		Trie_add(ns[i],i);
	Trie_getfail();
	for (int i=0; i<n; ++i)
		f[i]=true;
}

void Trie_getfail()
{
	que *head=new que, *tail, *temp;
	trie *tem;
	short t;
	head->x=root;
	head->next=NULL;
	tail=head;
	while (head!=NULL)
	{
		t=head->x->c-'a';
		if (head->x->father==root)
			head->x->fail=root;
		else
			if (head->x!=root)
			{
				tem=head->x->father->fail;
				while (true)
					if (tem==NULL)
					{
						head->x->fail=root;
						break;
					}
					else
						if (tem->p[t]!=NULL)
						{
							head->x->fail=tem->p[t];
							break;
						}
						else
							tem=tem->fail;
			}
		for (short i=0; i<26; ++i)
			if (head->x->p[i]!=NULL)
			{
				tail->next=new que;
				tail=tail->next;
				tail->x=head->x->p[i];
				tail->next=NULL;
			}
		temp=head;
		head=head->next;
		delete temp;
	}
}

void Match()
{
	int l;
	short t;
	trie *p;
	edge *temp;
	for (int i=0; i<m; ++i)
	{
		l=strlen(ms[i]);
		p=root;
		for (int j=0; j<l; ++j)
		{
			t=ms[i][j]-'a';
			while (p->p[t]==NULL && p!=root)
				p=p->fail;
			if (p->p[t]!=NULL)
				p=p->p[t];
			if (p->flag>=0)
			{
				ws[i]+=w[p->flag];
				temp=mapn[p->flag];
				mapn[p->flag]=new edge;
				mapn[p->flag]->x=i;
				mapn[p->flag]->next=temp;
				temp=mapm[i];
				mapm[i]=new edge;
				mapm[i]->x=p->flag;
				mapm[i]->next=temp;
			}
			if (p!=root)
				for (trie *k=p->fail; k!=root; k=k->fail)
					if (k->flag>=0)
					{
						ws[i]+=w[k->flag];
						temp=mapn[k->flag];
						mapn[k->flag]=new edge;
						mapn[k->flag]->x=i;
						mapn[k->flag]->next=temp;
						temp=mapm[i];
						mapm[i]=new edge;
						mapm[i]->x=k->flag;
						mapm[i]->next=temp;
					}
		}
	}
}

void Getheap()
{
	for (int i=1; i<=m; ++i)
	{
		h[i]=i-1;
		o[i-1]=i;
		for (int j=i; j>1 && ws[h[j]]<ws[h[j/2]]; j/=2)
			Swap(h[j],h[j/2]),
			Swap(o[h[j]],o[h[j/2]]);
	}
}

void Search()
{
	int t;
	for (int i=m-1; i>0; --i)
	{
		ans+=i*ws[h[1]];
		Swap(h[1],h[i+1]);
		Swap(o[h[1]],o[h[i+1]]);
		t=1;
		while (true)
			if (t*2>i)
				break;
			else
				if (t*2+1>i)
					if (ws[h[t*2]]<ws[h[t]])
					{
						Swap(h[t*2],h[t]);
						Swap(o[h[t*2]],o[h[t]]);
						t=t*2;
					}
					else
						break;
				else
					if (ws[h[t*2]]<ws[h[t*2+1]])
						if (ws[h[t*2]]<ws[h[t]])
						{
							Swap(h[t*2],h[t]);
							Swap(o[h[t*2]],o[h[t]]);
							t=t*2;
						}
						else
							break;
					else
						if (ws[h[t*2+1]]<ws[h[t]])
						{
							Swap(h[t*2+1],h[t]);
							Swap(o[h[t*2+1]],o[h[t]]);
							t=t*2+1;
						}
						else
							break;
		for (edge *j=mapm[h[i+1]]; j!=NULL; j=j->next)
			if (f[j->x])
			{
				f[j->x]=false;
				for (edge *k=mapn[j->x]; k!=NULL; k=k->next)
				{
					ws[k->x]-=w[j->x];
					for (int l=o[k->x]; l>1 && l<i && ws[h[l]]<ws[h[l/2]]; l/=2)
						Swap(h[l],h[l/2]),
						Swap(o[h[l]],o[h[l/2]]);
				}
			}
	}
}

void Output()
{
	freopen(O_F,"w",stdout);
	printf("%ld\n",ans);
}