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

Submission #634763

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,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 1;
}

Submission

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

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 0 / 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 0 / 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 27 ms 920 KB
sample_02.txt RE
subtask1_01.txt RE
subtask1_02.txt RE
subtask1_03.txt RE
subtask1_04.txt RE
subtask1_05.txt AC 30 ms 976 KB
subtask1_06.txt RE
subtask1_07.txt AC 28 ms 960 KB
subtask1_08.txt RE
subtask1_09.txt AC 31 ms 856 KB
subtask1_10.txt RE
subtask1_11.txt RE
subtask1_12.txt AC 29 ms 880 KB
subtask1_13.txt AC 35 ms 856 KB
subtask1_14.txt AC 31 ms 916 KB
subtask1_15.txt AC 33 ms 876 KB
subtask1_16.txt RE
subtask2_01.txt AC 101 ms 1900 KB
subtask2_02.txt RE
subtask2_03.txt AC 46 ms 2140 KB
subtask2_04.txt RE
subtask2_05.txt AC 39 ms 1960 KB
subtask2_06.txt RE
subtask2_07.txt AC 48 ms 2144 KB
subtask2_08.txt AC 82 ms 1888 KB
subtask2_09.txt RE
subtask2_10.txt AC 57 ms 1452 KB
subtask2_11.txt AC 1485 ms 1904 KB
subtask2_12.txt AC 459 ms 1888 KB
subtask2_13.txt AC 142 ms 1892 KB
subtask2_14.txt RE
subtask2_15.txt AC 256 ms 1880 KB
subtask2_16.txt RE
subtask2_17.txt RE
subtask2_18.txt TLE
subtask2_19.txt RE
subtask2_20.txt WA
subtask2_21.txt RE
subtask2_22.txt AC 1009 ms 1900 KB
subtask2_23.txt AC 33 ms 1892 KB
subtask2_24.txt RE
subtask2_25.txt AC 1003 ms 1884 KB
subtask2_26.txt AC 256 ms 1904 KB
subtask2_27.txt RE
subtask2_28.txt RE