Submission #1867539
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
inline void judge(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const int maxn=505,maxm=200005;
int head[maxm],t[maxm<<1],ne[maxm<<1],sap[maxm<<1],S,T,d[maxm],num;
int cur[maxm],cnt[maxm],his[maxm],edge[maxm],pre[maxm];
const int inf=1e6;
inline void addedge(int x,int y,int z){
ne[++num]=head[x];head[x]=num;t[num]=y;sap[num]=z;
ne[++num]=head[y];head[y]=num;t[num]=x;sap[num]=0;
}
inline int isap(){
rep(i,1,T)cur[i]=head[i],d[i]=0,cnt[i]=0;
cnt[0]=T;
int i=S,aug=inf,ans=0,minnum,jl;
while(d[S]<T){
bool flag=0;his[i]=aug;for(int j=cur[i];j!=-1;j=ne[j])if(d[t[j]]+1==d[i]&&sap[j]){
cur[i]=j;edge[i]=j;pre[t[j]]=i;aug=min(aug,sap[j]);flag=1;i=t[j];
if(i==T){
ans+=aug;
while(i!=S){i=pre[i];sap[edge[i]]-=aug;sap[edge[i]^1]+=aug;}
aug=inf;
}break;
}if(flag)continue;minnum=T;forE(j,i)if(sap[j]&&d[t[j]]<minnum)minnum=d[t[j]],jl=j;
if(--cnt[d[i]]==0)return ans;cnt[d[i]=minnum+1]++;cur[i]=jl;
if(i!=S){i=pre[i];aug=his[i];}
}return ans;
}
char s[maxn][maxn];
int n,m;
inline int tr(int x,int y){
return x*2+y;
}
int main(){
read(n);read(m);
rep(i,1,n)scanf("%s",s[i]+1);
S=n+m+1,T=S+1;
rep(i,1,T)head[i]=-1;num=1;
rep(i,1,n)rep(j,1,m){
if(s[i][j]=='S'){
addedge(S,i,inf);
addedge(S,j+n,inf);
}
if(s[i][j]=='T'){
addedge(i,T,inf);
addedge(j+n,T,inf);
}
if(s[i][j]=='o'){
addedge(i,j+n,1);
addedge(j+n,i,1);
}
}
int res=isap();
if(res>=inf){
puts("-1");
}else{
printf("%d\n",res);
}
return 0;
}
Submission Info
Submission Time
2017-12-12 19:30:35+0900
Task
F - Lotus Leaves
User
Scape
Language
C++14 (GCC 5.4.1)
Score
800
Code Size
2372 Byte
Status
AC
Exec Time
3 ms
Memory
8448 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:63:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i,1,n)scanf("%s",s[i]+1);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
800 / 800
Status
Set Name
Test Cases
Sample
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt
Case Name
Status
Exec Time
Memory
0_00.txt
AC
3 ms
8448 KB
0_01.txt
AC
3 ms
8448 KB
0_02.txt
AC
3 ms
8448 KB
0_03.txt
AC
3 ms
8448 KB
1_00.txt
AC
3 ms
8448 KB
1_01.txt
AC
3 ms
8448 KB
1_02.txt
AC
3 ms
8448 KB
1_03.txt
AC
3 ms
8448 KB
1_04.txt
AC
3 ms
8448 KB
1_05.txt
AC
3 ms
8448 KB
1_06.txt
AC
3 ms
8448 KB
1_07.txt
AC
2 ms
8448 KB
1_08.txt
AC
3 ms
8448 KB
1_09.txt
AC
3 ms
8448 KB
1_10.txt
AC
3 ms
8448 KB
1_11.txt
AC
3 ms
8448 KB
1_12.txt
AC
3 ms
8448 KB
1_13.txt
AC
3 ms
8448 KB
1_14.txt
AC
3 ms
8448 KB
1_15.txt
AC
3 ms
8448 KB
1_16.txt
AC
3 ms
8448 KB
1_17.txt
AC
2 ms
8448 KB
1_18.txt
AC
3 ms
8448 KB
1_19.txt
AC
3 ms
8448 KB
1_20.txt
AC
3 ms
8448 KB
1_21.txt
AC
3 ms
8448 KB
1_22.txt
AC
3 ms
8448 KB
1_23.txt
AC
3 ms
8448 KB
1_24.txt
AC
3 ms
8448 KB
1_25.txt
AC
3 ms
8448 KB
1_26.txt
AC
3 ms
8448 KB
1_27.txt
AC
3 ms
8448 KB
1_28.txt
AC
3 ms
8448 KB
1_29.txt
AC
3 ms
8448 KB
1_30.txt
AC
3 ms
8448 KB
1_31.txt
AC
3 ms
8448 KB
1_32.txt
AC
3 ms
8448 KB
1_33.txt
AC
3 ms
8448 KB
1_34.txt
AC
3 ms
8448 KB
1_35.txt
AC
3 ms
8448 KB
1_36.txt
AC
3 ms
8448 KB
1_37.txt
AC
3 ms
8448 KB
1_38.txt
AC
3 ms
8448 KB
1_39.txt
AC
3 ms
8448 KB
1_40.txt
AC
3 ms
8448 KB
1_41.txt
AC
3 ms
8448 KB
1_42.txt
AC
3 ms
8448 KB
1_43.txt
AC
3 ms
8448 KB
1_44.txt
AC
3 ms
8448 KB
1_45.txt
AC
3 ms
8448 KB
1_46.txt
AC
3 ms
8448 KB
1_47.txt
AC
3 ms
8448 KB
1_48.txt
AC
3 ms
8448 KB
1_49.txt
AC
3 ms
8448 KB