oj.uz

Submission #28338

# Submission time Handle Problem Language Result Execution time Memory
28338 2017-07-16T04:50:41 Z ㅁㄴㅇㄹ(#1150, TAMREF, Diuven, suhgyuho_william) Play Onwards (FXCUP2_onward) C++11
0 / 1
 0 ms 2200 KB 
#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};
int rep[mx],N,K;
int adj[mx][mx], vis[mx];
string S[mx];
set<pair<ll,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 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=0;j<N;j++){
            if(i!=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);
            }
        }
    }
}
int main(){
    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

onward.cpp: In function 'void input()':
onward.cpp:42: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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2200 KB Output is correct
2 Incorrect 0 ms 2200 KB Output isn't correct
3 Halted 0 ms 0 KB -