记录编号	378477	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000]病毒	最终得分	100
用户昵称	ONCE AGAIN	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2017-03-04 07:49:42	内存使用	2.61 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 100010;
int ch[maxn][2]={0},fail[maxn]={0},dan[maxn]={0};
int node = 0,q[maxn]={0},front = -1,back = 0;
void Insert(char *r){
	int n = strlen(r),now = 0;
	for(int i = 0;i < n;i++){
		if(!ch[now][r[i]-'0'])ch[now][r[i]-'0'] = ++node;
		now = ch[now][r[i]-'0'];
	}
	dan[now] = true;
}
void GetFail(){
	for(int i = 0;i <= 1;i++)
		if(ch[0][i])q[++front] = ch[0][i];
	while(back <= front){
		int now = q[back++];
		for(int i = 0;i <= 1;i++){
			int u = ch[now][i];
			if(!u){ch[now][i] = ch[fail[now]][i];continue;}
			q[++front] = u;
			if(dan[now])dan[u] = true;
			int temp = fail[now];
			while(temp && !ch[temp][i])temp = fail[temp];
			temp = ch[temp][i];
			fail[u] = temp;
			if(dan[fail[u]])dan[u] = true;
		}
	}
}
int du[maxn]={0};
bool ans = false;
void get(){
	back = 0;front = -1;
	for(int i = 0;i <= node;i++)if(!dan[i]){
		for(int j = 0;j <= 1;j++)du[ch[i][j]]++;
	}
	for(int i = 0;i <= node;i++)if(!dan[i] && !du[i])q[++front] = i;
	while(back <= front){
		int now = q[back++];//printf("now = %d\n",now);
		for(int i = 0;i <= 1;i++){
			int u = ch[now][i];
			du[u]--;
			if(!du[u] && !dan[u])q[++front] = u;
		}
	}
	for(int i = 0;i <= node&&!ans;i++)if(!dan[i]){
		if(du[i])ans = true;
	}
	if(ans)puts("TAK");
	else puts("NIE");
}

int N;char str[30100];
int main(){
	freopen("wir.in","r",stdin);
	freopen("wir.out","w",stdout);
	scanf("%d",&N);
	for(int i = 1;i <= N;i++){
		scanf("%s",str);
		Insert(str);
	}
	GetFail();
	get();
	return 0;
//	for(int i = 0;i <= node;i++)printf("dan[%d] = %d\n",i,dan[i]);
}