QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116330#4773. Piece it togethermomoyuuAC ✓141ms48116kbC++173.6kb2023-06-28 15:24:592023-06-28 15:25:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-28 15:25:03]
  • 评测
  • 测评结果:AC
  • 用时:141ms
  • 内存:48116kb
  • [2023-06-28 15:24:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template< typename flow_t >
struct Dinic {
    const flow_t INF;

    struct edge {
        int to;
        flow_t cap;
        int rev;
        bool isrev;
        int idx;
    };

    vector< vector< edge > > graph;
    vector< int > min_cost, iter;

    Dinic(int V) : INF(numeric_limits< flow_t >::max()), graph(V) {}

    void add_edge(int from, int to, flow_t cap, int idx = -1) {
        graph[from].emplace_back((edge) {to, cap, (int) graph[to].size(), false, idx});
        graph[to].emplace_back((edge) {from, 0, (int) graph[from].size() - 1, true, idx});
    }

    bool bfs(int s, int t) {
        min_cost.assign(graph.size(), -1);
        queue< int > que;
        min_cost[s] = 0;
        que.push(s);
        while(!que.empty() && min_cost[t] == -1) {
            int p = que.front();
            que.pop();
            for(auto &e : graph[p]) {
                if(e.cap > 0 && min_cost[e.to] == -1) {
                    min_cost[e.to] = min_cost[p] + 1;
                    que.push(e.to);
                }
            }
        }
        return min_cost[t] != -1;
    }

    flow_t dfs(int idx, const int t, flow_t flow) {
        if(idx == t) return flow;
        for(int &i = iter[idx]; i < graph[idx].size(); i++) {
            edge &e = graph[idx][i];
            if(e.cap > 0 && min_cost[idx] < min_cost[e.to]) {
                flow_t d = dfs(e.to, t, min(flow, e.cap));
                if(d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    flow_t max_flow(int s, int t) {
        flow_t flow = 0;
        while(bfs(s, t)) {
            iter.assign(graph.size(), 0);
            flow_t f = 0;
            while((f = dfs(s, t, INF)) > 0) flow += f;
        }
        return flow;
    }

    void output() {
        for(int i = 0; i < graph.size(); i++) {
            for(auto &e : graph[i]) {
                if(e.isrev) continue;
                auto &rev_e = graph[e.to][e.rev];
                cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
            }
        }
    }
};

void solve(){
    int n,m;
    cin>>n>>m;
    int h = n;int w = m;
    Dinic<int> dinic(2*n*m+2);
    int st = 2 * n * m;
    int t = st + 1;
    int a = 0;
    int b = 0;
    int dx[] = {1,-1,0,0};
    int dy[] = {0,0,1,-1};
    vector<string> s(n);
    for(int i = 0;i<n;i++) cin>>s[i];
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(s[i][j]=='.') continue;
            int ni = i * w + j;
            if(s[i][j]=='W'){
                a++;
                dinic.add_edge(ni,t,1);
                continue;
            }
            b++;
            dinic.add_edge(st,ni,1);
            dinic.add_edge(st,ni+n*m,1);
            for(int k = 0;k<4;k++){
                int nni = i + dx[k];
                int nnj = j + dy[k];
                if(nni<0||nni>=n||nnj<0||nnj>=m) continue;
                if(s[nni][nnj]!='W') continue;
                if(k<2) dinic.add_edge(ni,nni*w+nnj,1);
                else dinic.add_edge(ni+n*m,nni*w+nnj,1);
            }
        }
    }
    int can = dinic.max_flow(st,t);
    if(a==2*b&&can==a) cout<<"YES\n";
    else cout<<"NO\n";
                

}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3400kb

input:

2
3 4
BWW.
WWBW
..WB
3 3
W..
BW.
WBW

output:

YES
NO

result:

ok 2 token(s): yes count is 1, no count is 1

Test #2:

score: 0
Accepted
time: 141ms
memory: 48116kb

input:

70
3 4
BWW.
WWBW
..WB
3 3
W..
BW.
WBW
1 1
B
3 3
...
.W.
...
2 2
W.
BW
2 3
.W.
WBW
1 3
WBW
2 5
.W.W.
WB.BW
2 2
WW
.B
2 2
WB
..
3 3
WWB
BWW
WWB
3 5
.W.WB
WBW.W
...WB
4 5
..W..
.WBW.
WBWBW
.WBW.
3 9
BWW...W..
WWBW..BW.
..WB..WBW
4 12
BWWBWWBWWBWW
WWBWWBWWBWWB
BWWBWWBWWBWW
WWBWWBWWBWWB
7 7
BWWBBWW
WBWWW...

output:

YES
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
YES
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
NO
NO
NO
NO

result:

ok 70 token(s): yes count is 34, no count is 36