Submission #28369

#	Time	Username	Problem	Language	Result	Execution time	Memory
28369		ㅁㄴㅇㄹ (#68)	Play Onwards (FXCUP2_onward)	C++98	1 / 1	29 ms	2196 KiB

onward

#include <bits/stdc++.h>
#define va first
#define vb second
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
typedef long long ll;
using namespace std;
const int mx=205;
//const ll hbase[2]={1000000007,1610612741};
const ll hbase=1610612741;
ll pow26[mx]={1};
int rep[mx],N,K;
int adj[mx][mx], vis[mx];
string S[mx];
set<ll> Sh;
/*
bool compare(int i, int j){
    Sh.clear();
    int u=sz(S[i]), v=sz(S[j]);
    if(K>min(u,v)) return false;
    ll H[2]={0,0};
    for(int b=0;b<2;b++){
    for(int t=0;t<K;t++){
        H[b]=((H[b]*26)%hbase[b]+(S[i][t]-'a'))%hbase[b];
    }
    }
    Sh.insert(mp(H[0],H[1]));
    for(int t=K;t<u;t++){
        for(int b=0;b<2;b++) H[b]=(((H[b]*26%hbase[b])+(S[i][t]-'a'))%hbase[b]-(S[i][t-K]-'a')+hbase[b])%hbase[b];
        Sh.insert(mp(H[0],H[1]));
    }
    H[0]=H[1]=0;
    for(int t=0;t<K;t++){
        for(int b=0;b<2;b++) H[b]=((H[b]*26)%hbase[b]+(S[j][t]-'a'))%hbase[b];
    }
    if(Sh.find(mp(H[0],H[1]))!=Sh.end()) return true;
    for(int t=K;t<v;t++){
        for(int b=0;b<2;b++) H[b]=(((H[b]*26%hbase[b])+(S[j][t]-'a'))%hbase[b]-(S[j][t-K]-'a')+hbase[b])%hbase[b];
        if(Sh.find(mp(H[0],H[1]))!=Sh.end()) return true;
    }
    return false;
}*/
void buildpow(){
    for(int i=1;i<mx;i++) pow26[i]=pow26[i-1]*26%hbase;
}
bool compare(int i, int j){
    Sh.clear();
    int u=sz(S[i]), v=sz(S[j]);
    if(K>min(u,v)) return false;
    ll H=0;
    for(int t=0;t<K;t++){
        H=((H*26)%hbase+(S[i][t]-'a'))%hbase;
    }
    Sh.insert(H);
    for(int t=K;t<u;t++){
        H=(((H*26%hbase)+(S[i][t]-'a'))%hbase-((S[i][t-K]-'a')*pow26[K]%hbase)+hbase)%hbase;
        Sh.insert(H);
    }
    H=0;

    for(int t=0;t<K;t++){
        H=((H*26)%hbase+(S[j][t]-'a'))%hbase;
    }
    if(Sh.find(H)!=Sh.end()) return true;
    for(int t=K;t<v;t++){
        H=(((H*26%hbase)+(S[j][t]-'a'))%hbase-((S[j][t-K]-'a')*pow26[K]%hbase)+hbase)%hbase;
        if(Sh.find(H)!=Sh.end()) return true;
    }
    return false;
}
void input(){
    scanf("%d %d\n",&N,&K);
    for(int i=0;i<N;i++){
        getline(cin,S[i]);
    }
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            adj[i][j]=(adj[j][i]=compare(i,j));
        }
    }
}
void dfs(int x, int tg){
    for(int u=0;u<N;u++){
        if(adj[x][u]){
            if(vis[u]==tg) exit(0*puts("No"));
            if(!vis[u]){
                vis[u]=3-tg;
                dfs(u,3-tg);
            }
        }
    }
}
void debug(){
    for(int i=0;i<N;i++) cout<<S[i]<<endl;
    for(int i=0;i<N;i++,puts(""))
        for(int j=0;j<N;j++)
            printf("%d ",adj[i][j]);
}
int main(){
    //freopen("input.txt","rt",stdin);
    buildpow();
    input();
    int tg=1;
    for(int i=0;i<N;i++){
        if(!vis[i]){
            vis[i]=tg;
            dfs(i,tg);
        }
        tg=3-tg;
    }
    bool flag=true;
    for(int i=0;i<N;i++){
        flag=(flag&&(vis[i]==vis[0]));
    }
    if(flag) return 0*puts("No");
    puts("Yes");
    for(int i=0;i<N;i++){
        printf("%d\n",vis[i]);
    }
}

Compilation message (stderr)

onward.cpp: In function 'void input()':
onward.cpp:73:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d\n",&N,&K);
                           ^

• Subtask 1: 1 / 1