QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#663287#7857. (-1,1)-Sumpleteqzez#TL 24ms14572kbC++141.9kb2024-10-21 14:39:192024-10-21 14:39:20

Judging History

你现在查看的是最新测评结果

  • [2024-10-21 14:39:20]
  • 评测
  • 测评结果:TL
  • 用时:24ms
  • 内存:14572kb
  • [2024-10-21 14:39:19]
  • 提交

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
-++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...

output:


result: