QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#728730 | #7857. (-1,1)-Sumplete | Ashbourne | TL | 46ms | 12820kb | C++23 | 3.7kb | 2024-11-09 15:47:26 | 2024-11-09 15:47:35 |
Judging History
answer
#pragma GCC optimize(3)
#include<bits/stdc++.h>
const int N = 10005;
const int INF = 0x3f3f3f3f;
using namespace std;
int s, t, tot = 1, cnt;
struct Edge{
int next, to, cap, flow;
}edge[N * 10000];
int head[N];
void add(int u, int v, int w, int rw = 0){
edge[++tot] = {head[u], v, w, 0};
head[u] = tot;
edge[++tot] = {head[v], u, 0, 0};
head[v] = tot;
}
int maxflow = 0;
int dep[N], cur[N];
bool bfs(){
queue<int> q;
memset(dep, 0, sizeof (dep[0]) * (cnt + 1));
dep[s] = 1;
q.push(s);
while(q.size()){
int u = q.front();
q.pop();
for(int i = head[u]; i; i = edge[i].next){
int v = edge[i].to;
if((!dep[v]) && (edge[i].cap > edge[i].flow)){
dep[v] = dep[u] + 1;
if(v == t) return 1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u, int flow){
if((u == t) || (!flow)) return flow;
int ret = 0;
for(int &i = cur[u]; i; i = edge[i].next){
int v = edge[i].to, d;
if(dep[v] != dep[u] + 1) continue;
d = dfs(v, min(flow - ret, edge[i].cap - edge[i].flow));
if(d){
ret += d;
edge[i].flow += d;
edge[i ^ 1].flow -= d;
if(ret == flow) return ret;
}
}
return ret;
}
void dinic(){
while(bfs()){
memcpy(cur, head, sizeof (head[0]) * (cnt + 1));
maxflow += dfs(s, INF);
}
}
void solve(){
memset(head, 0, sizeof head);
// memset(dat, 0, sizeof dat);
// memset(vis, 0, sizeof vis);
tot = 1; // this is important
int n;
cin >> n;
s = 2 * n + 1; t = 2 * n + 2;
int x = 0, y = 0;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j){
char ch;
cin >> ch;
if(ch == '+'){
add(i, j + n, 1);
}else{
add(j + n, i, 1);
}
}
int ans = 0;
vector<int> a(n + 1), b(n + 1);
for(int i = 1; i <= n; ++ i) cin >> a[i], x += a[i];
for(int i = 1; i <= n; ++ i) cin >> b[i], y += b[i];
for(int i = 1; i <= n; ++ i){
if(a[i] > 0) ans += a[i];
if(a[i] > 0){
add(s, i, a[i]);
}else add(i, t, -a[i]);
}
for(int i = 1; i <= n; ++ i){
if(b[i] < 0) ans -= b[i];
if(b[i] < 0) add(s, i + n, -b[i]);
else add(i + n, t, b[i]);
}
cnt = 2 * n + 2;
tot = 1;
maxflow = 0;
// cout << ans << endl;
dinic();
if(ans != maxflow || x != y){
cout << "No" << endl;
}else{
cout << "Yes" << endl;
vector<vector<int>> vis(n + 10, vector<int>(n + 10));
for(int i = 1; i <= n; ++ i){
for(int j = head[i]; j; j = edge[j].next){
int v = edge[j].to;
if(v == s || v == t) continue;
v -= n;
// cout << i << " " << v << " " << j << endl;
if(edge[j].flow != 0){
vis[i][v] = 1;
}
}
}
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= n; ++ j) cout << vis[i][j];
// cout << "\n";
cout << endl;
}
}
}
int main(){
ios::sync_with_stdio(false);
int T = 1;
// cin >> T;
while(T--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 001 001 111
result:
ok n=3
Test #2:
score: 0
Accepted
time: 1ms
memory: 3664kb
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: 3728kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 00000000010000000100 00000000000010100010 00000000010000000100 00000011010000000100 00100000100101010001 00000000010000000000 00000000000101000101 00000000000000000001 00000000000000000000 00000100001100000001 00000001011100000101 00000000000101001000 10000000000001011000 00000000000001011000 00...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 2ms
memory: 4044kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010011010100010100000000000000000000000000000000000000000000011110110100010010011 0110011010111101000110101010100010100000000000000000000000000000000000000000101111110010111011101111 0010001101100110111000000010010010000000000000000000000000000000000000000000001011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 46ms
memory: 12820kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001010001001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok n=500
Test #9:
score: -100
Time Limit Exceeded
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...