oj.uz

Submission #1113

# Submission time Handle Problem Language Result Execution time Memory
1113 2013-06-25T13:39:00 Z lmj960417 백신 (KOI13_vaccine) C++
24 / 24
 34 ms 1328 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1328 KB Output is correct
2 Correct 0 ms 1328 KB Output is correct
3 Correct 0 ms 1328 KB Output is correct
4 Correct 0 ms 1328 KB Output is correct
5 Correct 0 ms 1328 KB Output is correct
6 Correct 0 ms 1328 KB Output is correct
7 Correct 0 ms 1328 KB Output is correct
8 Correct 0 ms 1328 KB Output is correct
9 Correct 0 ms 1328 KB Output is correct
10 Correct 0 ms 1328 KB Output is correct

Subtask #2
3.12 / 3.12

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1328 KB Output is correct
2 Correct 0 ms 1328 KB Output is correct
3 Correct 0 ms 1328 KB Output is correct
4 Correct 0 ms 1328 KB Output is correct
5 Correct 0 ms 1328 KB Output is correct
6 Correct 0 ms 1328 KB Output is correct
7 Correct 0 ms 1328 KB Output is correct
8 Correct 0 ms 1328 KB Output is correct
9 Correct 0 ms 1328 KB Output is correct
10 Correct 0 ms 1328 KB Output is correct

Subtask #3
3.6 / 3.6

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1328 KB Output is correct
2 Correct 0 ms 1328 KB Output is correct
3 Correct 0 ms 1328 KB Output is correct
4 Correct 0 ms 1328 KB Output is correct
5 Correct 0 ms 1328 KB Output is correct
6 Correct 0 ms 1328 KB Output is correct
7 Correct 0 ms 1328 KB Output is correct
8 Correct 0 ms 1328 KB Output is correct
9 Correct 1 ms 1328 KB Output is correct
10 Correct 0 ms 1328 KB Output is correct

Subtask #4
4.32 / 4.32

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1328 KB Output is correct
2 Correct 0 ms 1328 KB Output is correct
3 Correct 0 ms 1328 KB Output is correct
4 Correct 0 ms 1328 KB Output is correct
5 Correct 0 ms 1328 KB Output is correct
6 Correct 0 ms 1328 KB Output is correct
7 Correct 0 ms 1328 KB Output is correct
8 Correct 0 ms 1328 KB Output is correct
9 Correct 0 ms 1328 KB Output is correct
10 Correct 0 ms 1328 KB Output is correct

Subtask #5
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1328 KB Output is correct
2 Correct 2 ms 1328 KB Output is correct
3 Correct 4 ms 1328 KB Output is correct
4 Correct 33 ms 1328 KB Output is correct
5 Correct 2 ms 1328 KB Output is correct
6 Correct 3 ms 1328 KB Output is correct
7 Correct 2 ms 1328 KB Output is correct
8 Correct 9 ms 1328 KB Output is correct
9 Correct 12 ms 1328 KB Output is correct
10 Correct 12 ms 1328 KB Output is correct

Subtask #6
5.52 / 5.52

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1328 KB Output is correct
2 Correct 13 ms 1328 KB Output is correct
3 Correct 14 ms 1328 KB Output is correct
4 Correct 8 ms 1328 KB Output is correct
5 Correct 14 ms 1328 KB Output is correct
6 Correct 17 ms 1328 KB Output is correct
7 Correct 34 ms 1328 KB Output is correct
8 Correct 15 ms 1328 KB Output is correct
9 Correct 16 ms 1328 KB Output is correct
10 Correct 17 ms 1328 KB Output is correct