QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#289707 | #7857. (-1,1)-Sumplete | ucup-team296# | TL | 2176ms | 650164kb | C++14 | 3.7kb | 2023-12-23 21:28:50 | 2023-12-23 21:28:50 |
Judging History
answer
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
struct maxflow {
struct edge {
int src, dst, cap, flw;
};
vector<edge> edges;
vector<vector<int>> graph;
vector<int> first;
vector<int> dist;
maxflow(int n) {
graph.resize(n);
}
void bfs(int s) {
dist.assign(graph.size(), -1);
dist[s] = 0;
int h = 0;
vector<int> q;
q.push_back(s);
while (h < q.size()) {
int x = q[h++];
for (int i = 0; i < graph[x].size(); i++) {
edge& e = edges[graph[x][i]];
if (e.flw == e.cap) continue;
int y = e.dst;
if (dist[y] == -1) {
dist[y] = dist[x] + 1;
q.push_back(y);
}
}
}
}
int dfs(int x, int t, int f) {
if (f == 0) return 0;
if (x == t) return f;
for (int i = first[x]; i < graph[x].size(); i++) {
first[x] = i;
edge& e = edges[graph[x][i]];
edge& er = edges[graph[x][i] ^ 1];
if (e.flw == e.cap || dist[e.dst] != dist[e.src] + 1)
continue;
int y = e.dst;
int res = dfs(y, t, std::min(f, e.cap - e.flw));
if (res > 0) {
e.flw += res;
er.flw -= res;
return res;
}
}
return 0;
}
long maxFlow(int s, int t) {
long flow = 0;
while (true) {
bfs(s);
first.assign(graph.size(), 0);
if (dist[t] == -1) break;
while (true) {
int pushed = dfs(s, t, INT_MAX);
if (pushed > 0) {
flow += pushed;
} else {
break;
}
}
}
return flow;
}
void addEdge(int u, int v, int cap) {
// cout << u << " " << v << "\n";
edges.push_back({u, v, cap, 0});
edges.push_back({v, u, 0, 0});
graph[u].push_back(edges.size() - 2);
graph[v].push_back(edges.size() - 1);
}
};
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<string> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<int> r(n), c(n);
for (int i = 0; i < n; i++) cin >> r[i];
for (int i = 0; i < n; i++) cin >> c[i];
maxflow mf(2 * n + 2);
int s = 2 * n;
int t = 2 * n + 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == '+') {
mf.addEdge(i, n + j, 1);
} else {
mf.addEdge(n + j, i, 1);
}
}
}
int ff = 0;
for (int i = 0; i < n; i++) {
ff += abs(r[i]);
if (r[i] > 0) {
mf.addEdge(s, i, r[i]);
} else {
mf.addEdge(i, t, -r[i]);
}
}
for (int i = 0; i < n; i++) {
ff += abs(c[i]);
if (c[i] < 0) {
mf.addEdge(s, n + i, -c[i]);
} else {
mf.addEdge(n + i, t, c[i]);
}
}
int f = mf.maxFlow(s, t);
if (f * 2 != ff) {
cout << "No\n";
} else {
cout << "Yes\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int k = i * n + j;
if (mf.edges[k * 2].flw) {
cout << '1';
} else {
cout << '0';
}
}
cout << "\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3452kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 111 001 001
result:
ok n=3
Test #2:
score: 0
Accepted
time: 1ms
memory: 3524kb
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: 3524kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 01010001010000101110 00000000010010110010 10000100010001001100 10000011010001000111 11100000100001010000 10000000000000001001 01000000000101000100 01000010000000100110 00000000000000000000 10000000001100000001 00000001011100000101 00000000100000000000 00000000000011000000 00000000000001011000 00...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 2ms
memory: 3900kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 0100101011100001011000011010100111110111000101010110000000000000000100001100100111110010100010010011 1001100101000100001010101010101010101001010010011100010010000010000010110110101111110010111011101111 1101110010111011001000000010010110000001000001001000011111110010000110001100101001100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 20ms
memory: 13488kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 00101010110000011100101110100010100000001110011111101001100101011101111101110010100001101100011101100010011011011100111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100010000000...
result:
ok n=500
Test #9:
score: 0
Accepted
time: 1638ms
memory: 649948kb
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 00000000100001000000100000000010000001010010000100001000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok n=4000
Test #10:
score: 0
Accepted
time: 1674ms
memory: 649936kb
input:
4000 +---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...
output:
Yes 10001001101001101011001110011001110101010011111101101011101000111101011100001101000110011001110000011000110100111100001100110010101100100111110100011101110011110110111111100001110000010011011101101101110100111111010011001010001100000000101001100001011010110001001100101001011101001001111011000010...
result:
ok n=4000
Test #11:
score: 0
Accepted
time: 1723ms
memory: 650164kb
input:
4000 -+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...
output:
Yes 10110111111011000100111110011010010010010101000000110011010010100011100101000001000000101001001001010011101011111110010001001010000100101011111011110110111100001111111001011000111100000001011010111010000010111110011111110000110101001110000100001001000101001110110111010000001100111010000001010111...
result:
ok n=4000
Test #12:
score: 0
Accepted
time: 1589ms
memory: 649908kb
input:
4000 +-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...
output:
Yes 10100000111100000111101011010000111000110010001110101100000010101111000010111100101100001010001001000001011001101110001000111000110111000111100011000011100100010001110110101010011100110000110100000000000011001110010101101111110000101100100100111111110000011101110010010101010000100110110000111000...
result:
ok n=4000
Test #13:
score: 0
Accepted
time: 1654ms
memory: 649984kb
input:
4000 -+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...
output:
Yes 10001110111111101000010001001011001111000000111011100100001000100001011101100011111010110010110100001101100101110000000001000000010001101011100101001111010011001000000000000001000100100010010011101110001010001111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...
result:
ok n=4000
Test #14:
score: 0
Accepted
time: 2176ms
memory: 650068kb
input:
4000 +--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...
output:
Yes 01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010000000101100110000100101010011101101110111100101000110110110101010001010011...
result:
ok n=4000
Test #15:
score: 0
Accepted
time: 2124ms
memory: 650116kb
input:
4000 ---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...
output:
Yes 11011000110110100011111010000010000100010101010111111010110000010011111100001101100100110000001011000111100101101011011101101000011000001100001100000111001111100100000111000111100000101101100001001001010001001000110011011001001101110001001010001101111111001000110000110101001010111110000100111010...
result:
ok n=4000
Test #16:
score: -100
Time Limit Exceeded
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...