QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729011 | #7857. (-1,1)-Sumplete | nekoyellow | WA | 1ms | 3856kb | C++23 | 2.8kb | 2024-11-09 16:21:17 | 2024-11-09 16:21:18 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char nl = '\n';
class MF {
public:
MF(int _n, int _s, int _t): n(_n), s(_s), t(_t) {
head.assign(n, -1); dep.resize(n);
}
void addedge(int u, int v, int w) {
e.push_back({v, head[u], w, 0}); head[u] = e.size()-1;
e.push_back({u, head[v], 0, 0}); head[v] = e.size()-1;
}
ll dinic() {
ll maxflow = 0;
while (bfs()) cur = head, maxflow += dfs(s, inf);
return maxflow;
}
static const int inf = numeric_limits<int>::max();
int n, s, t;
struct Edge { int v, nxt, c, f; };
vector<Edge> e; vector<int> head;
vector<int> dep, cur;
bool bfs() {
queue<int> q; q.push(s);
fill(dep.begin(), dep.end(), 0); dep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if (!dep[v] && e[i].c > e[i].f) q.push(v), dep[v] = dep[u]+1;
}
}
return dep[t];
}
int dfs(int u, int flow) {
if (u == t || !flow) return flow;
int ret = 0;
for (int &i = cur[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if (dep[v] == dep[u]+1) {
int d = dfs(v, min(flow-ret, e[i].c-e[i].f));
if (!d) continue;
e[i].f += d, e[i^1].f -= d; ret += d;
if (ret == flow) break;
}
}
return ret;
}
};
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<string> g(n);
for (auto &s: g)
cin >> s;
vector<int> r(n), c(n);
for (auto &e: r)
cin >> e;
for (auto &e: c)
cin >> e;
int s = 2*n, t = 2*n+1;
MF mf(t+1, s, t);
int ans = 0;
for (int i = 0; i < n; i++) {
if (r[i] > 0) ans += r[i];
r[i] >= 0 ? mf.addedge(s, i, r[i]) : mf.addedge(i, t, -r[i]);
for (int j = 0; j < n; j++) {
g[i][j] == '+' ? mf.addedge(i, n+j, 1) : mf.addedge(n+j, i, 1);
}
}
for (int j = 0; j < n; j++) {
if (c[j] < 0) ans -= c[j];
c[j] >= 0 ? mf.addedge(n+j, t, c[j]) : mf.addedge(s, n+j, -c[j]);
}
if (ans != mf.dinic()) {
cout << "No\n";
} else {
cout << "Yes\n";
vector<string> ans(n, string(n, '0'));
for (int i = 0; i < n; i++) {
for (auto k = mf.head[i]; ~k; k = mf.e[k].nxt) {
int j = mf.e[k].v;
if (j == s || j == t) continue;
if (mf.e[k].f) ans[i][j-n] = '1';
}
}
for (auto &s: ans)
cout << s << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3664kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 001 001 111
result:
ok n=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
3 --- -++ +++ -2 -1 0 -2 -1 0
output:
Yes 110 100 000
result:
ok n=3
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3856kb
input:
1 - -1 1
output:
Yes 0
result:
wrong answer wrong sum at row 1