QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#532973 | #5071. Check Pattern is Good | liuziao | RE | 0ms | 3640kb | C++14 | 3.6kb | 2024-08-25 15:17:29 | 2024-08-25 15:17:29 |
Judging History
answer
#include <bits/stdc++.h>
#define int int64_t
const int kMaxN = 105, kInf = 1e18, kD[][2] = {{0, 1}, {0, -1}, {1, 0}, {1, -1}};
int n, m;
std::string s[105];
int getid(int x, int y, int o = 0) { return (x - 1) * m + y + o * n * m; }
namespace Dinic {
const int kMaxN = 3e4 + 5, kMaxM = 1e6 + 5;
struct Edge {
int v, w, pre;
} e[kMaxM];
int tot = 1, n, s, t, tail[kMaxN], cur[kMaxN], dep[kMaxN];
bool vis[kMaxN];
void set(int _n, int _s, int _t) { n = _n, s = _s, t = _t; }
void adde(int u, int v, int w) { e[++tot] = {v, w, tail[u]}, tail[u] = tot; }
void add(int u, int v, int w) { adde(u, v, w), adde(v, u, 0); }
void init() {
for (int i = 0; i <= tot; ++i) e[i] = {0, 0, 0};
for (int i = 0; i <= n; ++i) tail[i] = cur[i] = dep[i] = 0;
n = s = t = 0, tot = 1;
}
bool bfs() {
std::queue<int> q;
for (int i = 1; i <= n; ++i)
cur[i] = tail[i], dep[i] = kInf, vis[i] = 0;
q.emplace(s), dep[s] = 0, vis[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = tail[u]; i; i = e[i].pre) {
int v = e[i].v, w = e[i].w;
if (w && !vis[v]) {
dep[v] = dep[u] + 1, vis[v] = 1, q.emplace(v);
}
}
}
return vis[t];
}
int dfs(int u, int lim) {
if (u == t || !lim) return lim;
int flow = 0;
for (int &i = cur[u]; i; i = e[i].pre) {
int v = e[i].v, w = e[i].w;
if (w && dep[v] == dep[u] + 1) {
int fl = dfs(v, std::min(lim, w));
if (!fl) dep[v] = kInf;
lim -= fl, flow += fl;
e[i].w -= fl, e[i ^ 1].w += fl;
if (!lim) break;
}
}
return flow;
}
int maxflow() {
int ans = 0;
for (; bfs(); ans += dfs(s, kInf)) {}
return ans;
}
} // namespace Dinic
void dickdreamer() {
Dinic::init();
std::cin >> n >> m;
int ss = 3 * n * m + 1, tt = ss + 1, tot = 0;
Dinic::set(tt, ss, tt);
// 与 ss 相连:W,与 tt 相连 : B
for (int i = 1; i <= n; ++i) {
std::cin >> s[i];
s[i] = " " + s[i];
for (int j = 1; j <= m; ++j) {
if (((i + j) & 1) && s[i][j] != '?')
s[i][j] = 'B' + 'W' - s[i][j];
if (s[i][j] == '?') ++tot;
if (s[i][j] == '?' || s[i][j] == 'W') Dinic::add(ss, getid(i, j), 1);
else Dinic::add(ss, getid(i, j), kInf);
if (s[i][j] == '?' || s[i][j] == 'B') Dinic::add(getid(i, j), tt, 1);
else Dinic::add(getid(i, j), tt, kInf);
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j < n; ++j) {
int t1 = getid(i, j, 1), t2 = getid(i, j, 2);
Dinic::add(ss, t1, 1e9), Dinic::add(t2, tt, 1e9);
Dinic::add(t1, getid(i, j), kInf), Dinic::add(t1, getid(i, j + 1), kInf),
Dinic::add(t1, getid(i + 1, j), kInf), Dinic::add(t1, getid(i + 1, j + 1), kInf);
Dinic::add(getid(i, j), t2, kInf), Dinic::add(getid(i, j + 1), t2, kInf);
Dinic::add(getid(i + 1, j), t2, kInf), Dinic::add(getid(i + 1, j + 1), t2, kInf);
}
}
int cnt = Dinic::maxflow() - n * m;
assert(cnt % 1000000000 == 0);
// std::cerr << cnt << '\n';
std::cout << 2 * (n - 1) * (m - 1) - cnt / 1000000000 << '\n';
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (Dinic::vis[getid(i, j)]) s[i][j] = 'B';
else s[i][j] = 'W';
if ((i + j) & 1) s[i][j] = 'B' + 'W' - s[i][j];
std::cout << s[i][j];
}
std::cout << '\n';
}
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--) dickdreamer();
// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
input:
3 2 2 ?? ?? 3 3 BW? W?B ?BW 3 3 BW? W?W ?W?
output:
1 WB BW 1 BWW WWB WBW 4 BWB WBW BWB
result:
ok ok (3 test cases)
Test #2:
score: -100
Runtime Error
input:
10000 9 2 BB BW WW WW ?W ?B B? W? BB 6 2 ?? ?B B? BW WW ?? 10 7 WBBBW?? ???BWWW ???BWWB ??WWBW? BBWBBWB WWB?WW? BWBW??? WWWWBBW BBWBB?W B?W?W?B 4 7 ??WBWWB ?BBWWWB ?W?BBB? BBBWBBB 10 1 B W ? B B W W W B ? 10 4 ??WW W?W? WWW? ???W ?W?? ?W?W W?W? ?W?W ???W ???W 8 3 WBW W?? ??? ??? W?W W?W ??? ?W? 4 1 ...