QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710212 | #6398. Puzzle: Tapa | tassei903 | WA | 0ms | 3632kb | C++23 | 5.7kb | 2024-11-04 19:04:52 | 2024-11-04 19:04:53 |
Judging History
answer
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define rep(i, l, r) for (int i = l; i < (r); i++)
#define rrep(i, l, r) for(int i = (int)(r)-1; i >= (int)(l); i--)
#define all(x) begin(x), end(x)
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
struct mf_graph {
struct edge {
int from, to;
ll cap, flow;
};
struct nedge {
int to, rev;
ll cap;
};
int nn;
vector<pii> pos;
vector<vector<nedge>> g;
mf_graph() : nn(0) {}
explicit mf_graph(int n) : nn(n), g(n) {}
int add_edge(int from, int to, ll cap) {
int m = sz(pos);
pos.push_back({from, sz(g[from])});
int frid = sz(g[from]);
int toid = sz(g[to]);
if (from == to) toid ++ ;
g[from].push_back(nedge{to, toid, cap});
g[to].push_back(nedge{from, frid, 0});
return m;
}
ll flow(int s, int t) {
return flow(s, t, numeric_limits<ll>::max());
}
ll flow(int s, int t, ll flow_limit) {
vector<int> lv(nn), iter(nn);
queue<int> q;
auto bfs = [&]() {
fill(all(lv), -1);
lv[s] = 0;
queue<int>().swap(q);
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto e : g[v]) {
if (e.cap == 0 || lv[e.to] >= 0) continue;
lv[e.to] = lv[v] + 1;
if (e.to == t) return;
q.push(e.to);
}
}
};
auto dfs = [&](auto self, int v, ll up ) {
if (v == s) return up;
ll res = 0;
int lvvv = lv[v];
for (int& i = iter[v]; i < sz(g[v]); i ++ ) {
nedge& e = g[v][i];
if (lvvv <= lv[e.to] || g[e.to][e.rev].cap == 0)continue;
ll d = self(self, e.to, min(up - res, g[e.to][e.rev].cap));
if (d <= 0) continue;
g[v][i].cap += d;
g[e.to][e.rev].cap -= d;
res += d;
if (res == up) return res;
}
lv[v] = nn;
return res;
};
ll flow = 0;
while (flow < flow_limit) {
bfs();
if (lv[t] == -1) break;
fill(all(iter), 0);
ll f = dfs(dfs, t, flow_limit - flow);
if (!f) break;
flow += f;
}
return flow;
}
edge get_edge(int i) {
int m = int(pos.size());
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}
vector<edge> edges() {
int m = int(pos.size());
vector<edge> result;
for (int i = 0; i < m; i++) {
result.push_back(get_edge(i));
}
return result;
}
};
vector<int> dx = {1, 1, 1, 0, 0, -1, -1, -1}, dy = {-1, 0, 1, -1, 1, -1, 0, 1};
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int n, m;cin >> n >> m;
vector<string> s(n*2-1);rep(i, 0, n*2-1)cin >> s[i];
mf_graph mf(n * m + 2);int S = n * m, T = n * m + 1;
vector<string> ans = s;
auto get = [&](int u, int v) {
return s[u*2][v*2] - '0';
};
auto place_all = [&](int u, int v) {
rep(t, 0, 8) {
int x = u*2 + dx[t], y = v*2 + dy[t];
if (0 <= x && x < n*2 - 1 && 0 <= y && y < m*2-1)ans[x][y] = '#';
}
};
auto place_down = [&](int u, int v) {
place_all(u, v);
place_all(u+1, v);
ans[u*2+1][v*2] = '.';
};
auto place_right = [&](int u, int v) {
place_all(u, v);
place_all(u, v+1);
ans[u*2][v*2+1] = '.';
};
auto num = [&](int u, int v) {
return u * m + v;
};
auto connect = [&](int x, int y)->bool{
if (x > y)swap(x, y);
if (x == 2 && y == 2) return 1;
if (x == 2 && y == 4) return 1;
if (x == 4 && y == 4) return 1;
if (x == 7 && y == 7) return 1;
return 0;
};
int M1 = 0, M2 = 0;
rep(i, 0, n-1) rep(j, 0, m) {
if (connect(get(i, j), get(i+1, j))) {
if ((i+j) % 2)mf.add_edge(num(i, j), num(i+1, j), 1);
else mf.add_edge(num(i+1, j), num(i, j), 1);
M1++;
}
}
rep(i, 0, n) rep(j, 0, m-1) {
if (connect(get(i, j), get(i, j+1))) {
if ((i+j) % 2)mf.add_edge(num(i, j), num(i, j+1), 1);
else mf.add_edge(num(i, j+1), num(i, j), 1);
M2++;
}
}
int N = 0;
rep(i, 0, n) rep(j, 0, m) {
if (get(i, j) == 2 || get(i, j) == 4 || get(i, j) == 7) {
N += 1;
if ((i+j) % 2) mf.add_edge(S, num(i, j), 1);
else mf.add_edge(num(i, j), T, 1);
}
else {
place_all(i, j);
}
}
ll flow = mf.flow(S, T);
// cout << flow << endl;
rep(i, 0, M1) {
auto e = mf.get_edge(i);
if (e.cap) {
int I = min(e.from, e.to);
place_down(I/m, I%m);
}
}
rep(i, M1, M1+M2) {
auto e = mf.get_edge(i);
if (e.cap) {
int I = min(e.from, e.to);
place_right(I/m, I%m);
}
}
if (N == flow * 2) {
cout << "YES" << endl;
for(auto x:ans) {
cout << x << endl;
}
}
else {
cout << "NO" << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
3 3 2.4.3 ..... 5.8.5 ..... 3.5.3
output:
YES 2.4#3 ##### 5#8#5 ##### 3#5#3
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
3 3 3.4.3 ..... 5.7.5 ..... 3.5.3
output:
NO
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
2 2 2.2 ... 2.2
output:
YES 2.2 ### 2.2
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3576kb
input:
2 50 2.4.4.4.4.5.5.5.5.5.5.5.5.4.5.5.4.4.5.5.5.5.4.5.5.5.5.5.4.4.5.4.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.4.5.3 ................................................................................................... 2.5.5.4.4.5.5.5.4.4.5.5.5.4.5.5.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.5.4.4.5.5.5.5.4...
output:
YES 2#4#4#4.4#5#5#5#5#5#5#5#5#4#5#5#4.4#5#5#5#5#4#5#5#5#5#5#4.4#5#4#5#5#5#5#5#5#5#5#5#5#5#4.4#5#5#4#5#3 ##########################.###################################################################.#### 2#5#5#4.4#5#5#5#4.4#5#5#5#4#5#5#5#5#5#5#5#5#4#4.4#5#5#5#5#5#5#4#4.4#5#5#5#5#5#5#5#4.4#5#5#5#5#4#...
result:
wrong answer Clue not satisfied at (1,1)