Submission #634763
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 1;
}
Submission Info
Submission Time
2016-02-11 22:39:57+0900
Task
B - コメント
User
Kmcode
Language
C++11 (GCC 4.8.1)
Score
0
Code Size
2836 Byte
Status
WA
Exec Time
2007 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
0 / 30
0 / 60
Status
AC
× 21
WA
× 1
TLE
× 1
RE
× 21
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
27 ms
920 KB
sample_02.txt
RE
26 ms
916 KB
subtask1_01.txt
RE
28 ms
872 KB
subtask1_02.txt
RE
49 ms
920 KB
subtask1_03.txt
RE
51 ms
920 KB
subtask1_04.txt
RE
45 ms
920 KB
subtask1_05.txt
AC
30 ms
976 KB
subtask1_06.txt
RE
30 ms
904 KB
subtask1_07.txt
AC
28 ms
960 KB
subtask1_08.txt
RE
45 ms
936 KB
subtask1_09.txt
AC
31 ms
856 KB
subtask1_10.txt
RE
53 ms
872 KB
subtask1_11.txt
RE
46 ms
920 KB
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
47 ms
864 KB
subtask2_01.txt
AC
101 ms
1900 KB
subtask2_02.txt
RE
1678 ms
1904 KB
subtask2_03.txt
AC
46 ms
2140 KB
subtask2_04.txt
RE
84 ms
2160 KB
subtask2_05.txt
AC
39 ms
1960 KB
subtask2_06.txt
RE
1489 ms
2116 KB
subtask2_07.txt
AC
48 ms
2144 KB
subtask2_08.txt
AC
82 ms
1888 KB
subtask2_09.txt
RE
1769 ms
1856 KB
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
1679 ms
1876 KB
subtask2_15.txt
AC
256 ms
1880 KB
subtask2_16.txt
RE
1465 ms
1776 KB
subtask2_17.txt
RE
777 ms
1900 KB
subtask2_18.txt
TLE
2007 ms
1944 KB
subtask2_19.txt
RE
1268 ms
1896 KB
subtask2_20.txt
WA
34 ms
1896 KB
subtask2_21.txt
RE
951 ms
1896 KB
subtask2_22.txt
AC
1009 ms
1900 KB
subtask2_23.txt
AC
33 ms
1892 KB
subtask2_24.txt
RE
1364 ms
1900 KB
subtask2_25.txt
AC
1003 ms
1884 KB
subtask2_26.txt
AC
256 ms
1904 KB
subtask2_27.txt
RE
1918 ms
2020 KB
subtask2_28.txt
RE
1974 ms
1892 KB