Submission #3014650
Source Code Expand
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ;
struct edge{int to;int cap;int rev;};
struct Dinic{
private:
int n;
vector<vector<edge>> v;
vector<int> dist,iter;
public:
Dinic(int sz):n(sz),v(sz),dist(sz),iter(sz){}
void addedge(int from,int to,int cap){
int x=v[to].size(),y=v[from].size();
v[from].push_back({to,cap,x});
v[to].push_back({from,0,y});
}
void bfs(int s){
fill(dist.begin(),dist.end(),-1);
queue<int> q;
dist[s]=0;
q.push(s);
while(q.size()){
int x=q.front();q.pop();
rep(i,v[x].size()){
edge &e=v[x][i];
if(e.cap>0&&dist[e.to]<0){
dist[e.to]=dist[x]+1;
q.push(e.to);
}
}
}
}
int dfs(int x,int t,int f){
if(x==t)return f;
for(int& i=iter[x];i<(int)v[x].size();++i){
edge& e=v[x][i];
if(e.cap>0&&dist[x]<dist[e.to]){
int d=dfs(e.to,t,min(f,e.cap));
if(d>0){
e.cap-=d;
v[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t){
int flow=0;
while(1){
bfs(s);
if(dist[t]<0)return flow;
fill(iter.begin(),iter.end(),0);
int f;
while((f=dfs(s,t,inf))>0)flow+=f;
}
}
};
int main(){
int h,w;
cin>>h>>w;
Dinic dn(h+w+2);
string s[h];
rep(i,h){
cin>>s[i];
rep(j,w){
if(s[i][j]=='S'){
dn.addedge(h+w, i, inf);
dn.addedge(h+w, h+j, inf);
}
if(s[i][j]=='T'){
dn.addedge(i,h+w+1, inf);
dn.addedge(h+j,h+w+1, inf);
}
if(s[i][j]=='o'){
dn.addedge(i, h+j, 1);
dn.addedge(h+j, i, 1);
}
}
}
int ans=dn.max_flow(h+w, h+w+1);
cout<<(ans>=inf?-1:ans)<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Lotus Leaves |
User |
tempura0224 |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
2707 Byte |
Status |
AC |
Exec Time |
3 ms |
Memory |
896 KB |
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 |
1 ms |
256 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
1 ms |
256 KB |
0_03.txt |
AC |
1 ms |
256 KB |
1_00.txt |
AC |
1 ms |
256 KB |
1_01.txt |
AC |
1 ms |
256 KB |
1_02.txt |
AC |
1 ms |
256 KB |
1_03.txt |
AC |
1 ms |
256 KB |
1_04.txt |
AC |
2 ms |
256 KB |
1_05.txt |
AC |
2 ms |
640 KB |
1_06.txt |
AC |
3 ms |
896 KB |
1_07.txt |
AC |
2 ms |
256 KB |
1_08.txt |
AC |
2 ms |
640 KB |
1_09.txt |
AC |
3 ms |
896 KB |
1_10.txt |
AC |
2 ms |
384 KB |
1_11.txt |
AC |
2 ms |
384 KB |
1_12.txt |
AC |
2 ms |
256 KB |
1_13.txt |
AC |
2 ms |
512 KB |
1_14.txt |
AC |
2 ms |
512 KB |
1_15.txt |
AC |
2 ms |
640 KB |
1_16.txt |
AC |
2 ms |
384 KB |
1_17.txt |
AC |
2 ms |
384 KB |
1_18.txt |
AC |
2 ms |
384 KB |
1_19.txt |
AC |
2 ms |
512 KB |
1_20.txt |
AC |
2 ms |
512 KB |
1_21.txt |
AC |
2 ms |
256 KB |
1_22.txt |
AC |
2 ms |
512 KB |
1_23.txt |
AC |
2 ms |
512 KB |
1_24.txt |
AC |
2 ms |
256 KB |
1_25.txt |
AC |
2 ms |
512 KB |
1_26.txt |
AC |
2 ms |
512 KB |
1_27.txt |
AC |
2 ms |
384 KB |
1_28.txt |
AC |
2 ms |
384 KB |
1_29.txt |
AC |
2 ms |
384 KB |
1_30.txt |
AC |
2 ms |
384 KB |
1_31.txt |
AC |
2 ms |
640 KB |
1_32.txt |
AC |
2 ms |
512 KB |
1_33.txt |
AC |
2 ms |
256 KB |
1_34.txt |
AC |
2 ms |
512 KB |
1_35.txt |
AC |
2 ms |
512 KB |
1_36.txt |
AC |
2 ms |
512 KB |
1_37.txt |
AC |
2 ms |
512 KB |
1_38.txt |
AC |
2 ms |
512 KB |
1_39.txt |
AC |
2 ms |
640 KB |
1_40.txt |
AC |
2 ms |
384 KB |
1_41.txt |
AC |
2 ms |
640 KB |
1_42.txt |
AC |
2 ms |
256 KB |
1_43.txt |
AC |
2 ms |
384 KB |
1_44.txt |
AC |
1 ms |
256 KB |
1_45.txt |
AC |
2 ms |
384 KB |
1_46.txt |
AC |
2 ms |
384 KB |
1_47.txt |
AC |
2 ms |
256 KB |
1_48.txt |
AC |
2 ms |
384 KB |
1_49.txt |
AC |
2 ms |
512 KB |