Submission #1113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113		lmj960417	백신 (KOI13_vaccine)	C++98	24 / 24	34 ms	1328 KiB

vaccine

#include <stdio.h>
int n,m;
int ba[110][1010],len[110];
int data[1010],table[1010];
int rsw;
void kmp()
{
	int i,j;
	i=1;
	j=0;
	while(i<=n)
	{
		if(j==0 || data[i]==data[j])
		{
			i++;j++;
			table[i]=j;
		}
		else if(data[i]!=data[j]) j=table[j];
	}
}
int main()
{
	int i,a,j,s;

	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	scanf("%d %d",&n,&m);

	for(i=1;i<=n;i++)
	{
		scanf("%d",&len[i]);
		for(a=1;a<=len[i];a++)
		{
			scanf("%d ",&ba[i][a]);
		}
	}

	int sw=0;
	for(s=1;s<=len[1];s++)
	{
		if(s+m-1>len[1]) break;
		for(i=1;i<=m;i++)
		{
			data[i]=ba[1][s+i-1];
		}
		kmp();
		for(a=2;a<=n;a++)
		{
			i=1;
			j=1;
			sw=0;
			while(i<=len[a])
			{
				if(j==0 || ba[a][i]==data[j])
				{
					i++;j++;
				}
				else if(ba[a][i]!=data[j]) j=table[j];
				if(j>m)
				{
					sw=1;
					break;
				}
			}
			if(!sw)
			{
				i=len[a];
				j=1;
				while(i>0)
				{
					if(j==0 || ba[a][i]==data[j])
					{
						i--;j++;
					}
					else if(ba[a][i]!=data[j]) j=table[j];
					if(j>m)
					{
						sw=1;
						break;
					}
				}
			}
			if(!sw) break;
		}
		if(a>n)
		{
			printf("YES\n");
			rsw=1;
			break;
		}
	}

	if(!rsw) printf("NO\n");

	return 0;
}

• Subtask 1: 2.64 / 2.64
• Subtask 2: 3.12 / 3.12
• Subtask 3: 3.6 / 3.6
• Subtask 4: 4.32 / 4.32
• Subtask 5: 4.8 / 4.8
• Subtask 6: 5.52 / 5.52