Submission #803104

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}

int N;
vint lis[26][101010];
char S[101010];

vector<int>G[400];
int match[400];
bool used[400];

void add_edge(int u,int v){
    G[u].pb(v);
    G[v].pb(u);
}

bool dfs(int v){
    used[v]=true;
    for(int i=0;i<G[v].size();i++){
        int u=G[v][i];
        int u_pair=match[u];
        if(u_pair<0||(!used[u_pair]&&dfs(u_pair))){
            match[v]=u;
            match[u]=v;
            return true;
        }
    }
    return false;
}

void init(){
    rep(i,N*2)G[i].clear();
}

int bipartite_matching(){
    int res=0;
    memset(match,-1,sizeof(match));
    for(int v=0;v<N*2;v++){
        if(match[v]<0){
            memset(used,0,sizeof(used));
            if(dfs(v)){
                res++;
            }
        }
    }
    return res;
}



signed main(){
    scanf("%lld",&N);
    for(int i=0;i<N;i++){
        scanf("%s",S);
        for(int j=0;S[j];j++){
            lis[S[j]-'a'][j].pb(i);
        }
    }

    for(int c=0;c<26;c++){
        int cnt=0;
        for(int i=0;i<N-1;i++)if(lis[c][i].size())cnt++;
        for(int i=0;i+N<=101010;i++){
            if(lis[c][i+N-1].size())cnt++;
            if(cnt==N){
                init();
                for(int j=0;j<N;j++){
                    for(int k=0;k<lis[c][i+j].size();k++){
                        add_edge(j,lis[c][i+j][k]+N);
                    }
                }
                if(bipartite_matching()==N){
                    cout<<"YES"<<endl;
                    return 0;
                }
            }
            if(lis[c][i].size())cnt--;
        }
    }
    cout<<"NO"<<endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&N);
                     ^
./Main.cpp:68:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",S);
                      ^

Judge Result