Submission #28675

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28675	2017-07-16T08:35:52 Z	Fe(#1116, minchurl)	Play Onwards (FXCUP2_onward)	C++	0 / 1	9 ms	36484 KB

onward

#include<stdio.h>
#include<string.h>
#define N 2005
int n,k,net[N][N],b[N][N],drg[N],chk[N],m[N],f[N],cnt;
char s[N][N];
int kmp(int x,int y,int ss,int e){
    int i,j;
    i=j=0;
    while(i<m[y]){
        while(j+1 && s[y][i]-s[x][j+ss])    j=f[j];
        i++;j++;
        if(j==k)   return 1;
    }
    return 0;
}
void make_f(int x,int ss,int e){
    int i,j;
    i=0;j=-1;
    f[i]=j;
    while(i<k){
        while(j+1 && s[x][i+ss]-s[x][j+ss])    j=f[j];
        i++;j++;
        f[i]=j;
    }
}
int is_ok(int x,int y){
    int ss,e,i,j;
    for(ss=0;ss<m[x]-k+1;ss++){
        e=ss+k-1;
        make_f(x,ss,e);
        if(kmp(x,y,ss,e))   return 1;
    }
    return 0;
}
int main(){
    int i,j,h;
    scanf("%d %d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%s",s[i]);
        m[i]=strlen(s[i]);
    }
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            if(is_ok(i,j))  continue;
            net[i][j]=net[j][i]=1;
        }
    }

    cnt=0;
    for(i=1;i<=n;i++){
        if(chk[i])  continue;
        chk[i]=++cnt;
        b[cnt][drg[cnt]++]=i;
        for(j=i+1;j<=n;j++){
            if(chk[j])  continue;
            for(h=0;h<drg[cnt];h++){
                if(!net[j][b[cnt][h]])  break;
            }

            if(h-drg[cnt])  continue;
            chk[j]=cnt;
            b[cnt][drg[cnt]++]=j;
        }
    }
    if(cnt==1){
        printf("Yes\n");
        printf("2\n");
        for(i=2;i<=n;i++)   printf("1\n");
    }else if(cnt==2){
        printf("Yes\n");
        for(i=1;i<=n;i++)   printf("%d\n",chk[i]);
    }else{
        printf("No\n");
    }
    return 0;
}

Compilation message

onward.cpp: In function 'int is_ok(int, int)':
onward.cpp:27:14: warning: unused variable 'i' [-Wunused-variable]
     int ss,e,i,j;
              ^
onward.cpp:27:16: warning: unused variable 'j' [-Wunused-variable]
     int ss,e,i,j;
                ^
onward.cpp: In function 'int main()':
onward.cpp:37:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
                         ^
onward.cpp:39:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",s[i]);
                         ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	36484 KB	Output is correct
2	Correct	0 ms	36484 KB	Output is correct
3	Correct	0 ms	36484 KB	Output is correct
4	Correct	0 ms	36484 KB	Output is correct
5	Correct	0 ms	36484 KB	Output is correct
6	Correct	0 ms	36484 KB	Output is correct
7	Correct	9 ms	36484 KB	Output is correct
8	Correct	9 ms	36484 KB	Output is correct
9	Incorrect	9 ms	36484 KB	Output isn't correct
10	Halted	0 ms	0 KB	-