Submission #1160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160		kriii	백신 (KOI13_vaccine)	C++98	24 / 24	31 ms	1688 KiB

vaccine

#include <stdio.h>

int N,K,M[101],X[101][1010],R[101][1010],PI[1010];

int main()
{
	int i,j,k,l;

	scanf ("%d %d",&N,&K);
	for (i=0;i<N;i++){
		scanf ("%d",&M[i]);
		for (j=0;j<M[i];j++) scanf ("%d",&X[i][j]), R[i][M[i]-j-1] = X[i][j];
	}

	for (i=0;i<M[0]-K+1;i++){
		PI[0] = k = -1;
		for (j=1;j<K;j++){
			while (k != -1 && X[0][i+j] != X[0][i+k+1]) k = PI[k];
			if (X[0][i+j] == X[0][i+k+1]) k++;
			PI[j] = k;
		}
		for (l=1;l<N;l++){
			k = -1;
			for (j=0;j<M[l];j++){
				while (k != -1 && X[l][j] != X[0][i+k+1]) k = PI[k];
				if (X[l][j] == X[0][i+k+1]) k++;
				if (k == K - 1) break;
			}
			if (k == K - 1) continue;
			k = -1;
			for (j=0;j<M[l];j++){
				while (k != -1 && R[l][j] != X[0][i+k+1]) k = PI[k];
				if (R[l][j] == X[0][i+k+1]) k++;
				if (k == K - 1) break;
			}
			if (k == K - 1) continue;
			break;
		}

		if (l == N){printf ("YES"); return 0;}
	}
	printf ("NO");
	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