QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#728730#7857. (-1,1)-SumpleteAshbourneTL 46ms12820kbC++233.7kb2024-11-09 15:47:262024-11-09 15:47:35

Judging History

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

  • [2024-11-09 15:47:35]
  • 评测
  • 测评结果:TL
  • 用时:46ms
  • 内存:12820kb
  • [2024-11-09 15:47:26]
  • 提交

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

output:


result: