Submission #3014607


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,(1LL<<31)-1))>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 0
Code Size 2713 Byte
Status WA
Exec Time 3 ms
Memory 896 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 4
AC × 48
WA × 6
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 WA 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 WA 2 ms 640 KB
1_42.txt AC 2 ms 256 KB
1_43.txt WA 2 ms 384 KB
1_44.txt AC 1 ms 256 KB
1_45.txt WA 2 ms 384 KB
1_46.txt WA 2 ms 384 KB
1_47.txt AC 2 ms 256 KB
1_48.txt WA 2 ms 384 KB
1_49.txt AC 2 ms 512 KB