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
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
AC × 4
AC × 54
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