Submission #337993

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <utility>
#include <complex>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
const int MAX_V=400;
int V;				//substitute!!
vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];
void add_edge(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}
bool dfs(int v){
	used[v]=true;
	rep(i,G[v].size()){
		int u=G[v][i],w=match[u];
		if(w<0 || (!used[w] && dfs(w))){
			match[v]=u;
			match[u]=v;
			return true;
		}
	}
	return false;
}
int nibu(){
	int res=0;
	memset(match,-1,sizeof(match));
	rep(v,V){
		if(match[v]<0){
			memset(used,0,sizeof(used));
			if(dfs(v)) res++;
		}
	}
	return res;
}
int N;
string s[200];
vector<int> nums;
bool solve(){
	cin>>N;
	V=2*N;
	rep(i,N) cin>>s[i];
	rep(i,N) nums.pb(s[i].size());
	sort(all(nums));
	int mn=1e9;
	rep(i,N) mn=min(mn,nums[i]-i);
	rep(c,26){
		for(int i=0;i<mn;){
			rep(j,V) G[j].clear();
			rep(j,N) rep(k,N){
				if(s[j].size()>k+i&&s[j][k+i]=='a'+c) add_edge(j,k+N);
			}
			int a=nibu();
			if(a==N) return true;
			i+=N-a;
		}
	}
	return false;
}
int main(){
	if(solve()) puts("YES");
	else puts("NO");
}

Submission Info

Judge Result