QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#291942 | #7857. (-1,1)-Sumplete | ucup-team045# | TL | 2775ms | 461992kb | C++20 | 3.9kb | 2023-12-27 14:25:51 | 2023-12-27 14:25:51 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<limits>
using namespace std;
using LL = long long;
const int maxn = 1e5 + 5, maxm = 3.5e7 + 5;
template<typename flow_t>
struct MaxFlow{
const flow_t INF = numeric_limits<flow_t>::max() / 2;
int h[maxn], e[maxm], ne[maxm], idx;
flow_t f[maxm];
int cur[maxn], q[maxn], d[maxn];
int V, S, T;
void init(int v, int s, int t){
for(int i = 0; i <= v; i++) h[i] = -1;
idx = 0;
V = v, S = s, T = t;
}
void add(int a, int b, flow_t c, flow_t d = 0){
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = d, ne[idx] = h[b], h[b] = idx++;
}
bool bfs(){
for(int i = 0; i <= V; i++) d[i] = -1;
int hh = 0, tt = -1;
q[++tt] = S, d[S] = 0, cur[S] = h[S];
while(hh <= tt){
int t = q[hh++];
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if (d[j] == -1 && f[i]){
d[j] = d[t] + 1;
cur[j] = h[j];
if (j == T) return true;
q[++tt] = j;
}
}
}
return false;
}
flow_t find(int u, flow_t limit){
if (u == T) return limit;
flow_t flow = 0;
// start from cur[u] instead of h[u] <- important
for(int i = cur[u]; ~i && flow < limit; i = ne[i]){
int j = e[i];
cur[u] = i;
if (d[j] == d[u] + 1 && f[i]){
flow_t t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
else f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
flow_t dinic(){
flow_t res = 0, flow;
while(bfs()) while(flow = find(S, INF)) res += flow;
return res;
}
};
MaxFlow<int> flow;
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
vector<string> g(n);
for(int i = 0; i < n; i++) cin >> g[i];
vector<int> a(n), b(n);
int sum1 = 0, sum2 = 0;
for(int i = 0; i < n; i++)
cin >> a[i], sum1 += a[i];
for(int i = 0; i < n; i++)
cin >> b[i], sum2 += b[i];
if (sum1 != sum2){
cout << "No" << '\n';
return 0;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if (g[i][j] == '-'){
sum1 += 1;
sum2 += 1;
a[i] += 1;
b[j] += 1;
}
}
}
int s = 2 * n, t = 2 * n + 1;
flow.init(2 * n + 1, s, t);
for(int i = 0; i < n; i++){
if (a[i] < 0){
cout << "No" << '\n';
return 0;
}
flow.add(s, i, a[i]);
}
for(int i = 0; i < n; i++){
if (b[i] < 0){
cout << "No" << '\n';
return 0;
}
flow.add(i + n, t, b[i]);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
flow.add(i, j + n, 1);
}
}
if (flow.dinic() != sum1){
cout << "No" << '\n';
return 0;
}
vector<vector<int> > ans(n, vector<int>(n));
for(int x = 0; x < n; x++){
for(int i = flow.h[x]; ~i; i = flow.ne[i]){
int j = flow.e[i];
if (j >= n && j < 2 * n && !flow.f[i]){
ans[x][j - n] = 1;
}
}
}
cout << "Yes" << '\n';
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if (g[i][j] == '-'){
ans[i][j] ^= 1;
}
cout << ans[i][j];
}
cout << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9948kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 111 001 001
result:
ok n=3
Test #2:
score: 0
Accepted
time: 2ms
memory: 9796kb
input:
3 --- -++ +++ -2 -1 0 -2 -1 0
output:
Yes 110 100 000
result:
ok n=3
Test #3:
score: 0
Accepted
time: 1ms
memory: 7724kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 7908kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 9936kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 10000011011111011011 01011111111001010110 01110011110110100000 01110101111110011101 11101010100010110001 10100000111101001001 01001011100111100111 01010001001101000111 00000100110000000111 11111100110001011001 00001111111111100111 10101000001011011100 11101110001011011100 01000010100001011100 01...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 0ms
memory: 8060kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010100101011000001000111011010110101110000000101100101100100111110110100010010011 0110011010111101000110010101010101010101010010011100010010000010000010110110101111110010111011101111 0010001101100110111000111101101001111110111001001000011111111010011111001100101011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 11ms
memory: 15248kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 00101010110000011100101110100010100000011111001100101101100011001001001011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...
result:
ok n=500
Test #9:
score: 0
Accepted
time: 2456ms
memory: 460828kb
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 01101010100101111000101100000011000101110011100111111100010110111111100001000111011001100010110010000100010011010101000001010001001000100011101111010000011001101101011010011101001001010000111011111011101010001110110100101001100111100010100110001010001000111010000101001100010000010100100001111101...
result:
ok n=4000
Test #10:
score: 0
Accepted
time: 2342ms
memory: 459744kb
input:
4000 +---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...
output:
Yes 10001001101001101011001110011001110101010011111101101011101000111101011100001101000110011001110000011000110100111100001100110010101100100111110100011101110011110111111110100001010100010011011101101101110100011111110011001010001100000000101001100001011010110001001100100001011101001101111011000011...
result:
ok n=4000
Test #11:
score: 0
Accepted
time: 2463ms
memory: 461188kb
input:
4000 -+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...
output:
Yes 01001000000100111011000001100101101101101010111111001100101101011100011010111110111111010110110110101100010100000001101110110101111011010100000100001001000011110000000110100111000011111110100101000101111101000001100000001111001010110001111011110110111010110001001000101111110011000101111110101000...
result:
ok n=4000
Test #12:
score: 0
Accepted
time: 2339ms
memory: 461992kb
input:
4000 +-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...
output:
Yes 10100000111100000111101011010000111000110010001110101100000010101111000010111100101100001010001001000001011001101110001000111000110111000111100011000011100100010001110110101010011100110000110100000011101101100100111000100000001111010110011010010000001111100010001101111011101111010001101111000011...
result:
ok n=4000
Test #13:
score: 0
Accepted
time: 2375ms
memory: 460628kb
input:
4000 -+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...
output:
Yes 01110001000000010111101110110100110000111111000100011011110111011110100010011100000101001101001011110010011010001111111110111111101110010100011010110000101100110111111111111110111011011101101100010001110101111111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...
result:
ok n=4000
Test #14:
score: 0
Accepted
time: 2100ms
memory: 461112kb
input:
4000 +--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...
output:
Yes 10011111001100101110110101010100110000001111000111010100100000011010011010111000001011111010000001111011110101100000011001111101010010111111111111111011010101000100011111011001000011100101110101110100110001011110101011011011011100100110101100111111110011111110101100100001111111111100011000010010...
result:
ok n=4000
Test #15:
score: 0
Accepted
time: 2775ms
memory: 461728kb
input:
4000 ---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...
output:
Yes 00011011010100001101111000000000001110011110110110010100100101011110011011001111100110010100001010001101110100101111111101100011110100101110001010010010100100111111010001111110111100001010101100100010010111001111110111010001001000000000001101110011111110011011111001110101111111110010001110010100...
result:
ok n=4000
Test #16:
score: -100
Time Limit Exceeded
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...