Submission #16234

#	Time	Username	Problem	Language	Result	Execution time	Memory
16234		eaststar	백신 (KOI13_vaccine)	C++14	24 / 24	456 ms	1528 KiB

vaccine

#include <stdio.h>
int a[110][1010],l[110],p[1010],pi[1010],chk[1010],k;
void ff(){
    int i=0,j=-1;
    pi[0]=-1;
    while(i<k){
        if(j<0||p[i]==p[j])++i,++j,pi[i]=j;
        else j=pi[j];
    }
}
int kmp(int n){
    int i=0,j=-1;
    while(i<l[n]){
        if(j<0||a[n][i]==p[j])++i,++j;
        else j=pi[j];
        if(j>=k)return 1;
    }
    return 0;
}
int main(){
    int i,j,n,s;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i){
        scanf("%d",l+i);
        for(j=0;j<l[i];++j)scanf("%d",a[i]+j);
    }
    for(i=0;i<l[1]-k;++i){
        for(j=0;j<k;++j)p[j]=a[1][i+j];
        ff();
        s=1;
        for(j=2;j<=n;++j)chk[j]=0;
        for(j=2;j<=n;++j)if(kmp(j))++s,chk[j]=1;
        for(j=0;j<k;++j)p[k-j-1]=a[1][i+j];
        ff();
        for(j=2;j<=n;++j)if(!chk[j]&&kmp(j))++s;
        if(s==n)break;
    }
    if(i<l[1]-k)puts("YES");
    else puts("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