QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729046 | #7857. (-1,1)-Sumplete | KobicGend | WA | 1ms | 3856kb | C++23 | 3.4kb | 2024-11-09 16:25:11 | 2024-11-09 16:25:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n'
struct MaxFlow {
vector<vector<array<int, 3>>> E;
vector<int> level, curr;
MaxFlow(int n): E(n), level(n), curr(n) {}
void add(int u, int v, int w) {
E[u].push_back({ w, v, int(E[v].size()) });
E[v].push_back({ 0, u, int(E[u].size()) - 1 });
}
bool bfs(int s, int t) {
queue<int> q;
fill(level.begin(), level.end(), 0);
fill(curr.begin(), curr.end(), 0);
level[s] = 1;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for (auto& [w, v, id] : E[u]) {
if (w && !level[v]) {
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[t] > 0;
}
int dfs(int u, int t, int maxf) {
if (u == t) return maxf;
for (int& i = curr[u]; i < E[u].size(); i++) {
auto& [w, v, id] = E[u][i];
if (w && (level[v] == level[u] + 1)) {
int f = dfs(v, t, min(maxf, w));
if (f) {
w -= f;
E[v][id][0] += f;
curr[u] = i;
return f;
}
}
}
return 0;
}
int dinic(int s, int t) {
int ans = 0;
while (bfs(s, t)) {
while (int f = dfs(s, t, 1e9)) {
ans += f;
}
}
return ans;
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n;
cin >> n;
MaxFlow maxflow(2 * n + 5);
vector num(n + 2, vector<int>(n + 2));
int s = 2 * n + 2;
int t = s + 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
char x;
cin >> x;
if(x == '+') {
num[i][j] = 1;
maxflow.add(i, j + n, 1);
} else {
maxflow.add(j + n, i, 1);
}
}
}
ll sum = 0;
for(int i = 1; i <= n; i++){
int tmp;
cin >> tmp;
if(tmp > 0) {
maxflow.add(s, i, tmp);
sum += tmp;
} else if (tmp < 0) {
maxflow.add(i, t, -tmp);
}
}
for(int j = 1; j <= n; j++){
int tmp;
cin >> tmp;
if(tmp > 0) {
maxflow.add(j + n, t, tmp);
} else if (tmp < 0) {
sum -= tmp;
maxflow.add(s, j + n, -tmp);
}
}
vector ans(n + 2, vector<int>(n + 2));
ll flow = maxflow.dinic(s, t);
//cerr << "flow == " << flow << endl;
if (flow == sum) {
cout << "Yes" << endl;
for (int u = 1; u <= n; u++){
for (auto& [w, v, id] : maxflow.E[u]){
if(v >= (n + 1) && v <= (2 * n) && w != num[u][v - n]) {
//cerr << "u == " << u << " v == " << v << " w == " << w << endl;
ans[u][v - n] = 1;
}
}
}
for (int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cout << ans[i][j];
}
cout << endl;
}
} else {
cout << "No" << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 111 001 001
result:
ok n=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3784kb
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: 3856kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3564kb
input:
1 - -1 1
output:
Yes 0
result:
wrong answer wrong sum at row 1