QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#116330 | #4773. Piece it together | momoyuu | AC ✓ | 141ms | 48116kb | C++17 | 3.6kb | 2023-06-28 15:24:59 | 2023-06-28 15:25:03 |
Judging History
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