oj.uz

Submission #28710

# Submission time Handle Problem Language Result Execution time Memory
28710 2017-07-16T08:57:18 Z Fe(#1116, minchurl) Play Onwards (FXCUP2_onward) C++
0 / 1
 9 ms 1492 KB 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 205
int n,k,net[N][N],b[N][N],drg[N],chk[N],m[N],f[N],cnt,p,q;
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;
    if(m[x]<k || m[y]<k)    return 0;
    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;
}
void ff(int x,int y){
    int i;
    chk[x]=y;
    for(i=1;i<=n;i++){
        if(!net[x][i])   continue;
        if(net[x][i] && chk[i]==y){
            printf("No\n");
            exit(0);
        }
        if(chk[i]==((p==y)?q:p))  continue;
        ff(i,((p==y)?q:p));
    }
}
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))  net[i][j]=net[j][i]=1;
            else    net[i][j]=net[j][i]=0;
        }
    }
    for(i=1;i<=n;i++){
        if(chk[i])  continue;
        cnt+=2;
        p=cnt-1;
        q=cnt;
        ff(i,p);
    }
    p=chk[1];
    for(i=1;i<=n;i++){
        if(p-chk[i])    break;
        p=chk[i];
    }
    if(i==n+1){
        printf("Yes\n");
        printf("2\n");
        for(i=2;i<=n;i++)   printf("1\n");
    }else{
        printf("Yes\n");
        for(i=1;i<=n;i++)   printf("%d\n",chk[i]%2+1);
    }
    return 0;
}

Compilation message

onward.cpp: In function 'int is_ok(int, int)':
onward.cpp:28:14: warning: unused variable 'i' [-Wunused-variable]
     int ss,e,i,j;
              ^
onward.cpp:28:16: warning: unused variable 'j' [-Wunused-variable]
     int ss,e,i,j;
                ^
onward.cpp: In function 'int main()':
onward.cpp:51:13: warning: unused variable 'h' [-Wunused-variable]
     int i,j,h;
             ^
onward.cpp:52: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:54: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 Correct 0 ms 1492 KB Output is correct
6 Correct 0 ms 1492 KB Output is correct
7 Correct 9 ms 1492 KB Output is correct
8 Correct 9 ms 1492 KB Output is correct
9 Correct 9 ms 1492 KB Output is correct
10 Correct 6 ms 1492 KB Output is correct
11 Incorrect 3 ms 1492 KB Output isn't correct
12 Halted 0 ms 0 KB -