记录编号	73887	评测结果	AAAAAAAAAA
题目名称	[NOI 2000]单词查找树	最终得分	100
用户昵称	ranto	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2013-10-23 13:19:32	内存使用	0.31 MiB

#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#define itn int

using namespace std;

ifstream in("trie.in");
ofstream out("trie.out");

long ans(1);
vector<string> vs;

void input();
void proc();
void output();

int main()
{
	input(); 
	proc();  
	output();
	return 0;
}

void input()
{
	while(!in.eof())
	{
		register string stemp;
		in>>stemp;
		if(stemp=="")
		{
			continue;
		}
		vs.push_back(stemp);
	}
	return ;
}

struct node
{
	int start;
	int end;
	int depth;
};

node make(itn a,itn b,itn c)
{
	node ret;
	ret.start=a;
	ret.end=b;
	ret.depth=c;
	return ret;
}

void bfs()
{
	queue<node> q;
	int start(0);
	itn end(-1);
	char comp(vs[0][0]);
	for(int i=0;i!=vs.size();++i)
	{
		if(vs[i][0]==comp)
		{
			++end;
			if(vs[i].size()<=1)
			{
				++start;
			}
			continue;
		}
		else
		{
			++ans;
			comp=vs[i][0];
			if(start>end)
			{
				start=i;
				end=i-1;
				--i;
				continue;
			}
			if(start==end)
			{
				start=i;
				end=i-1;
				--i;
				ans+=vs[start-1].size()-1;
				continue;
			}
			q.push(make(start,end+1,1));
			start=i;
			end=i-1;
			--i;
		}
	}
	++ans;
	if(start==end)
	{
		ans+=vs[start].size()-1;
	}
	else if(start<end)
	{
		q.push(make(start,end+1,1));//[min,max)
	}
	while(!q.empty())
	{
		node n;
		n=q.front();
		q.pop();
		//out<<n.start<<' '<<n.end-1<<endl;
		start=(n.start);
		end=(n.start-1);
		int depth(n.depth);
		comp=vs[start][depth];
		for(int i=start;i!=n.end;++i)
		{
			if(vs[i][depth]==comp)
			{
				++end;
				if(vs[i].size()<=depth+1)
				{
					++start;
				}
				continue;
			}
			else
			{
				++ans;
				comp=vs[i][depth];
				if(start>end)
				{
					start=i;
					end=i-1;
					--i;
					continue;
				}
				if(start==end)
				{
					start=i;
					end=i-1;
					--i;
					ans+=vs[start-1].size()-1-depth;
					continue;
				}
				q.push(make(start,end+1,depth+1));
				start=i;
				end=i-1;
				--i;
			}
		}
		++ans;
		if(start==end)
		{
			ans+=vs[start].size()-depth-1;
		}
		else if(start<end)
		{
			q.push(make(start,end+1,depth+1));//[min,max)
		}
	}
	return ;
}

void proc()
{
	if(vs.size()==1)
	{
		ans+=vs[0].size();
		return ;
	}
	stable_sort(vs.begin(),vs.end());
	/*for(itn i=0;i!=vs.size();++i)
	{
		out<<vs[i]<<endl;
	}*/
	bfs();
	return ;
}

void output()
{
	out<<ans<<endl;
	return ;
}