Submission #634771
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,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 Info
Submission Time
2016-02-11 22:46:15+0900
Task
B - コメント
User
Kmcode
Language
C++11 (GCC 4.8.1)
Score
90
Code Size
2834 Byte
Status
AC
Exec Time
1775 ms
Memory
2160 KB
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
Set Name
Sample
Subtask1
Subtask2
Score / Max Score
0 / 0
30 / 30
60 / 60
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt
Subtask1
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
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
Case Name
Status
Exec Time
Memory
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