oj.uz

Submission #1160

# Submission time Handle Problem Language Result Execution time Memory
1160 2013-06-28T11:16:43 Z kriii 백신 (KOI13_vaccine) C++
24 / 24
 31 ms 1688 KB 
#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

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

Subtask #2
3.12 / 3.12

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

Subtask #3
3.6 / 3.6

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

Subtask #4
4.32 / 4.32

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

Subtask #5
4.8 / 4.8

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

Subtask #6
5.52 / 5.52

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1688 KB Output is correct
2 Correct 12 ms 1688 KB Output is correct
3 Correct 14 ms 1688 KB Output is correct
4 Correct 6 ms 1688 KB Output is correct
5 Correct 10 ms 1688 KB Output is correct
6 Correct 13 ms 1688 KB Output is correct
7 Correct 31 ms 1688 KB Output is correct
8 Correct 12 ms 1688 KB Output is correct
9 Correct 17 ms 1688 KB Output is correct
10 Correct 17 ms 1688 KB Output is correct