Submission #634761

---

Source Code Expand

/*
 * d.cpp
 *
 *  Created on: 2016/02/11
 *      Author: joi
 */
#include<bits/stdc++.h>
using namespace std;

#define MAX 202

int n;
char buf[100002];

vector<pair<int,int> > ich[26];


class MaxFlow{
	struct st{
		int from;
		int to;
		int cap;
		int rev;
		st(int from_,int to_,int cap_,int rev_){
			from=from_;
			to=to_;
			cap=cap_;
			rev=rev_;
		}
	};
	vector<st> ed[MAX*2];
public:
	void add_edge(int from,int to,int cap){
		int r=ed[to].size();
		int rr=ed[from].size();
		ed[from].push_back(st(from,to,cap,r));
		ed[to].push_back(st(to,from,cap,rr));
	}
private:
	int level[MAX*2];
	int itr[MAX*2];
public:
	void init(){
		for(int i=0;i<n*2+2;i++){
			ed[i].clear();
		}
	}
private:
	void init2(){
		for(int i=0;i<n*2+2;i++){
			level[i]=-1;
			itr[i]=0;
		}
	}
	queue<int> q;
	void bfs(int star){
		level[star]=0;
		q.push(star);
		while(!q.empty()){
			int b=q.front();
			q.pop();
			int siz=ed[b].size();
			for(int i=0;i<siz;i++){
				if(ed[b][i].cap==0){
					continue;
				}
				int &go=ed[b][i].to;
				if(level[go]==-1){
					level[go]=level[b]+1;
					q.push(go);
				}
			}
		}
	}
	inline int dfs(int b,int &en,int fl=-1){
		if(b==en){
			return fl;
		}
		int siz=ed[b].size();
		for(int &i=itr[b];i<siz;i++){
			st &f=ed[b][i];
			if(f.cap==0){
				continue;
			}
			if(level[b]>=level[f.to]){
				continue;
			}
			int nex_cost=f.cap;
			if(fl!=-1&&nex_cost>fl){
				nex_cost=fl;
			}
			int r=dfs(ed[b][i].to,en,nex_cost);
			if(r==-1){
				continue;
			}
			ed[ed[b][i].to][ed[b][i].rev].cap+=r;
			ed[ed[b][i].from][i].cap-=r;
			return r;
		}
		return -1;
	}
public:
	int maxflow(int s,int t){
		int answer=0;
		while(1){
			init2();
			bfs(s);
			if(level[t]==-1){
				return answer;
			}
			while(1){
				int k=dfs(s,t);
				if(k<=0){
					break;
				}
				answer+=k;
				continue;
			}
		}
		return 0;
	}
};

void solve(vector<pair<int,int > > &v){
	int siz=v.size();
	int pr=-1;
	MaxFlow ff;
	for(int i=0;i<siz;i++){
		if(pr==v[i].first){
			continue;
		}
		pr=v[i].first;
		ff.init();
		int star=0;
		int en=2*n+1;
		for(int j=i;j<siz&&v[j].first<v[i].first+n;j++){
			ff.add_edge(1+v[j].second,1+n+(v[j].first-v[i].first),1);
		}
		for(int i1=0;i1<n;i1++){
			ff.add_edge(star,1+i1,1);
			ff.add_edge(n+1+i1,en,1);
		}
		if(ff.maxflow(star,en)==n){
			puts("YES");
			exit(0);
		}
	}
}

vector<string> v;
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%s",buf);
		v.push_back(buf);
	}
	for(int i=0;i<n;i++){
		int siz=v[i].size();
		for(int j=0;j<siz;j++){
			ich[v[i][j]-'a'].push_back(make_pair(j,i));
		}
	}
	for(int i=0;i<26;i++){
		sort(ich[i].begin(),ich[i].end());
		solve(ich[i]);
	}
	puts("NO");
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:152:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:154:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",buf);
                  ^

Judge Result