QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729197 | #7857. (-1,1)-Sumplete | ANeutrino | TL | 1677ms | 513520kb | C++23 | 3.5kb | 2024-11-09 16:40:37 | 2024-11-09 16:40:41 |
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 sums = 0, sumt = 0;
for (int i = 1; i <= n; i++) {
int tmp;
cin >> tmp;
if (tmp > 0) {
maxflow.add(s, i, tmp);
sums += tmp;
} else if (tmp < 0) {
sumt -= tmp;
maxflow.add(i, t, -tmp);
}
}
for (int j = 1; j <= n; j++) {
int tmp;
cin >> tmp;
if (tmp > 0) {
sumt += tmp;
maxflow.add(j + n, t, tmp);
} else if (tmp < 0) {
sums -= 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 == sums && sums == sumt) {
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: 0ms
memory: 3576kb
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: 3560kb
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: 3612kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 3644kb
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: 1ms
memory: 4048kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 0100101011100001011000011010100111110111000101010110000000000000000100001100100111110010100010010011 1001100101000100001010101010101010101001010010011100010010000010000010110110101111110010111011101111 1101110010111011001000000010010110000001000001001000011111110010000110001100101001100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 20ms
memory: 11316kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 00101010110000011100101110100010100000001110011111101001100101011101111101110010100001101100011101100010011011011100111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100010000000...
result:
ok n=500
Test #9:
score: 0
Accepted
time: 1247ms
memory: 513440kb
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 00000000100001000000100000000010000001010010000100001000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok n=4000
Test #10:
score: 0
Accepted
time: 1319ms
memory: 513348kb
input:
4000 +---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...
output:
Yes 10001001101001101011001110011001110101010011111101101011101000111101011100001101000110011001110000011000110100111100001100110010101100100111110100011101110011110110111111100001110000010011011101101101110100111111010011001010001100000000101001100001011010110001001100101001011101001001111011000010...
result:
ok n=4000
Test #11:
score: 0
Accepted
time: 1320ms
memory: 513516kb
input:
4000 -+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...
output:
Yes 10110111111011000100111110011010010010010101000000110011010010100011100101000001000000101001001001010011101011111110010001001010000100101011111011110110111100001111111001011000111100000001011010111010000010111110011111110000110101001110000100001001000101001110110111010000001100111010000001010111...
result:
ok n=4000
Test #12:
score: 0
Accepted
time: 1276ms
memory: 513420kb
input:
4000 +-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...
output:
Yes 10100000111100000111101011010000111000110010001110101100000010101111000010111100101100001010001001000001011001101110001000111000110111000111100011000011100100010001110110101010011100110000110100000000000011001110010101101111110000101100100100111111110000011101110010010101010000100110110000111000...
result:
ok n=4000
Test #13:
score: 0
Accepted
time: 1234ms
memory: 513424kb
input:
4000 -+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...
output:
Yes 10001110111111101000010001001011001111000000111011100100001000100001011101100011111010110010110100001101100101110000000001000000010001101011100101001111010011001000000000000001000100100010010011101110001010001111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...
result:
ok n=4000
Test #14:
score: 0
Accepted
time: 1677ms
memory: 513364kb
input:
4000 +--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...
output:
Yes 01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010000000101100110000100101010011101101110111100101000110110110101010001010011...
result:
ok n=4000
Test #15:
score: 0
Accepted
time: 1641ms
memory: 513520kb
input:
4000 ---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...
output:
Yes 11011000110110100011111010000010000100010101010111111010110000010011111100001101100100110000001011000111100101101011011101101000011000001100001100000111001111100100000111000111100000101101100001001001010001001000110011011001001101110001001010001101111111001000110000110101001010111110000100111010...
result:
ok n=4000
Test #16:
score: -100
Time Limit Exceeded
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...