oj.uz

Submission #28669

# Submission time Handle Problem Language Result Execution time Memory
28669 2017-07-16T08:34:43 Z Fe(#1116, minchurl) Play Onwards (FXCUP2_onward) C++
0 / 1
 0 ms 1492 KB 
#include<stdio.h>
#include<string.h>
#define N 205
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;
        }
    }
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            if(m[i]-m[j])   continue;
            for(h=0;h<m[i];h++){
                if(s[i][h]-s[j][h]) break;
            }
            if(h-m[i])  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 1492 KB Output is correct
2 Correct 0 ms 1492 KB Output is correct
3 Correct 0 ms 1492 KB Output is correct
4 Correct 0 ms 1492 KB Output is correct
5 Incorrect 0 ms 1492 KB Output isn't correct
6 Halted 0 ms 0 KB -