dwangoプログラミングコンテスト

Submission #634771

Source codeソースコード

/*
 * 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,0,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

Task問題 B - コメント
User nameユーザ名 Kmcode
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 90
Source lengthソースコード長 2834 Byte
File nameファイル名
Exec time実行時間 1775 ms
Memory usageメモリ使用量 2160 KB

Compiler messageコンパイルメッセージ

./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);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
Subtask1 30 / 30 sample_01.txt,sample_02.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt
Subtask2 60 / 60 subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask2_01.txt,subtask2_02.txt,subtask2_03.txt,subtask2_04.txt,subtask2_05.txt,subtask2_06.txt,subtask2_07.txt,subtask2_08.txt,subtask2_09.txt,subtask2_10.txt,subtask2_11.txt,subtask2_12.txt,subtask2_13.txt,subtask2_14.txt,subtask2_15.txt,subtask2_16.txt,subtask2_17.txt,subtask2_18.txt,subtask2_19.txt,subtask2_20.txt,subtask2_21.txt,subtask2_22.txt,subtask2_23.txt,subtask2_24.txt,subtask2_25.txt,subtask2_26.txt,subtask2_27.txt,subtask2_28.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 30 ms 800 KB
sample_02.txt AC 26 ms 920 KB
subtask1_01.txt AC 26 ms 924 KB
subtask1_02.txt AC 43 ms 928 KB
subtask1_03.txt AC 44 ms 924 KB
subtask1_04.txt AC 41 ms 920 KB
subtask1_05.txt AC 26 ms 1052 KB
subtask1_06.txt AC 25 ms 928 KB
subtask1_07.txt AC 26 ms 920 KB
subtask1_08.txt AC 43 ms 924 KB
subtask1_09.txt AC 26 ms 920 KB
subtask1_10.txt AC 46 ms 924 KB
subtask1_11.txt AC 42 ms 924 KB
subtask1_12.txt AC 27 ms 924 KB
subtask1_13.txt AC 27 ms 924 KB
subtask1_14.txt AC 28 ms 924 KB
subtask1_15.txt AC 25 ms 924 KB
subtask1_16.txt AC 42 ms 920 KB
subtask2_01.txt AC 122 ms 1888 KB
subtask2_02.txt AC 1697 ms 1948 KB
subtask2_03.txt AC 44 ms 2132 KB
subtask2_04.txt AC 79 ms 2160 KB
subtask2_05.txt AC 37 ms 1964 KB
subtask2_06.txt AC 1425 ms 2144 KB
subtask2_07.txt AC 47 ms 2156 KB
subtask2_08.txt AC 101 ms 1944 KB
subtask2_09.txt AC 1775 ms 1948 KB
subtask2_10.txt AC 52 ms 1436 KB
subtask2_11.txt AC 1506 ms 1904 KB
subtask2_12.txt AC 458 ms 1904 KB
subtask2_13.txt AC 135 ms 1904 KB
subtask2_14.txt AC 1708 ms 1944 KB
subtask2_15.txt AC 254 ms 1812 KB
subtask2_16.txt AC 1314 ms 1816 KB
subtask2_17.txt AC 628 ms 1896 KB
subtask2_18.txt AC 1544 ms 1860 KB
subtask2_19.txt AC 1023 ms 1944 KB
subtask2_20.txt AC 1162 ms 1900 KB
subtask2_21.txt AC 907 ms 1904 KB
subtask2_22.txt AC 974 ms 1952 KB
subtask2_23.txt AC 615 ms 1892 KB
subtask2_24.txt AC 1294 ms 1908 KB
subtask2_25.txt AC 969 ms 1900 KB
subtask2_26.txt AC 241 ms 1892 KB
subtask2_27.txt AC 1727 ms 1904 KB
subtask2_28.txt AC 1755 ms 1900 KB