QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297402 | #7857. (-1,1)-Sumplete | ucup-team870# | TL | 15ms | 18764kb | C++20 | 3.1kb | 2024-01-04 13:19:50 | 2024-01-04 13:19:50 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N = 10010;
struct edge {
int to, next, flow;
} ed[33000010];
int s, t, deep[N], head[N], cur[N], sz=-1, row[N], col[N];
char a[4040][4040];
bool ksj[4040][4040];
char tmp[N];
void addEdge(int from, int to, int flow) {
sz++;
ed[sz].to = to;
ed[sz].next = head[from];
ed[sz].flow = flow;
head[from] = sz;
}
void add(int u, int v, int f) {
addEdge(u, v, f);
addEdge(v, u, 0);
}
bool bfs() {
queue <int> q;
q.push(s);
memset(deep, 0, sizeof(deep));
deep[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i != -1; i = ed[i].next) {
int v = ed[i].to;
if (deep[v] == 0 && ed[i].flow > 0) {
deep[v] = deep[u] + 1;
q.push(v);
if (v == t) return true;
}
}
}
return false;
}
int dfs(int u, int flow) {
if (u == t) return flow;
int rest = flow;
for (int i = cur[u]; i != -1; i = ed[i].next) {
int v = ed[i].to;
if (deep[v] == deep[u] + 1 && ed[i].flow > 0 && rest) {
int now = dfs(v, min(ed[i].flow, rest));
if (!now) deep[v] = 0;
rest -= now;
ed[i].flow -= now;
ed[i^1].flow += now;
if (ed[i].flow) cur[u] = i;
if (rest == 0) break;
}
}
if (rest == flow) deep[u] = -1;
return flow - rest;
}
int dinic() {
int flow = 0;
while (bfs()) {
rep (i, 1, t) cur[i] = head[i];
flow += dfs(s, 1e9);
}
return flow;
}
int main() {
memset(head, -1, sizeof(head));
int n; scanf("%d", &n);
rep (i, 1, n) {
scanf("%s", tmp+1);
rep (j, 1, n) {
if (tmp[j] == '+') a[i][j] = 1;
}
}
rep (i, 1, n) {
scanf("%d", &row[i]);
}
rep (i, 1, n) {
scanf("%d", &col[i]);
}
rep (i, 1, n) {
rep (j, 1, n) {
if (!a[i][j]) {
row[i]++, col[j]++;
ksj[i][j] = 1;
}
add(i, j+n, 1);
}
}
s = 2*n+1, t = s+1;
int sumS = 0, sumT= 0 ;
rep (i, 1, n) {
add(s, i, row[i]);
sumS += row[i];
sumT += col[i];
add(i+n, t, col[i]);
}
int flow = dinic();
if (sumS == sumT && flow == sumS) {
puts("Yes");
rep (u, 1, n) {
for (int i = head[u]; i != -1; i = ed[i].next) {
int v = ed[i].to;
if (v != s) {
if (ed[i].flow == 0) ksj[u][v-n] ^= 1;
}
}
}
rep (i, 1, n) {
rep (j, 1, n) {
printf("%d", ksj[i][j]);
}
cout <<'\n';
}
} else {
puts("No");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8132kb
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: 7856kb
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: 7748kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 5692kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 9992kb
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: 2ms
memory: 10272kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010100101011000001000111011010110101110000000101100101100100111110110100010010011 0110011010111101000110010101010101010101010010011100010010000010000010110110101111110010111011101111 0010001101100110111000111101101001111110111001001000011111111010011111001100101011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 15ms
memory: 18764kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 00101010110000011100101110100010100000011111001100101101100011001001001011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...
result:
ok n=500
Test #9:
score: -100
Time Limit Exceeded
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 01101010100101111000101100000011000101110011100111111100010110111111100001000111011001100010110010000100010011010101000001010001001000100011101111010000011001101101011010011101001001010000111011111011101010001110110100101001100111100010100110001010001000111010000101001100010000010100100001111101...