QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#663287 | #7857. (-1,1)-Sumplete | qzez# | TL | 24ms | 14572kb | C++14 | 1.9kb | 2024-10-21 14:39:19 | 2024-10-21 14:39:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=4e3+10,V=N*2,E=N*N*2,INF=1e9;
int n,p[N],q[N];
char a[N][N];
struct edges{
int to,c,nex;
}edge[E];
int kk=1,s,t,head[V],cur[V],d[V];
void add(int u,int v,int c){
// cerr<<u<<' '<<v<<' '<<c<<endl;
edge[++kk]={v,c,head[u]},head[u]=kk;
edge[++kk]={u,0,head[v]},head[v]=kk;
}
bool bfs(){
queue<int>q;
copy(head+s,head+1+t,cur+s);
fill(d+s,d+1+t,-1);
d[s]=0,q.push(s);
for(int u;!q.empty();){
u=q.front(),q.pop();
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].to;
if(edge[i].c&&d[v]==-1)d[v]=d[u]+1,q.push(v);
}
}
return d[t]!=-1;
}
int dfs(int u,int lim=INF){
if(u==t)return lim;
int flow=0;
for(int i=cur[u];i&&flow<lim;i=edge[i].nex){
cur[u]=i;
int v=edge[i].to;
if(d[v]!=d[u]+1||!edge[i].c)continue;
int f=dfs(v,min(lim-flow,edge[i].c));
if(!f)d[v]=-1;
edge[i].c-=f,edge[i^1].c+=f,flow+=f;
}
return flow;
}
int dinic(){
int flow=0;
for(;bfs();)flow+=dfs(s);
return flow;
}
int id[N][N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
}
s=0,t=n+n+1;
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
if(p[i]>0){
sum+=p[i],add(s,i,p[i]);
}else{
add(i,t,-p[i]);
}
}
for(int i=1;i<=n;i++){
scanf("%d",&q[i]);
if(q[i]>0){
add(i+n,t,q[i]);
}else{
sum+=-q[i];
add(s,i+n,-q[i]);
}
}
if(accumulate(p+1,p+1+n,0)!=accumulate(q+1,q+1+n,0))puts("No"),exit(0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]=='+')add(i,j+n,1);
else add(j+n,i,1);
id[i][j]=kk-1;
}
}
int res=dinic();
if(res!=sum)puts("No"),exit(0);
puts("Yes");
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
putchar("01"[edge[id[i][j]^1].c]);
}
puts("");
}
// for(int u=s;u<=t;u++){
// for(int i=head[u];i;i=edge[i].nex){
// if(i%2==0&&edge[i^1].c)fprintf(stderr,"%d %d %d\n",u,edge[i].to,edge[i^1].c);
// }
// }
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7720kb
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: 7816kb
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: 8044kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 7672kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 7820kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 7896kb
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: 0ms
memory: 10232kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010011010100010100000000000000000000000000000000000000000000011110110100010010011 0110011010111101000110101010100010100000000000000000000000000000000000000000101111110010111011101111 0010001101100110111000000010010010000000000000000000000000000000000000000000001011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 24ms
memory: 14572kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001010001001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok n=500
Test #9:
score: -100
Time Limit Exceeded
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...