QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291941 | #7857. (-1,1)-Sumplete | ucup-team045# | RE | 19ms | 17948kb | C++20 | 3.9kb | 2023-12-27 14:25:00 | 2023-12-27 14:25:00 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<limits>
using namespace std;
using LL = long long;
const int maxn = 1e5 + 5, maxm = 1e7 + 5;
template<typename flow_t>
struct MaxFlow{
const flow_t INF = numeric_limits<flow_t>::max() / 2;
int h[maxn], e[maxm], ne[maxm], idx;
flow_t f[maxm];
int cur[maxn], q[maxn], d[maxn];
int V, S, T;
void init(int v, int s, int t){
for(int i = 0; i <= v; i++) h[i] = -1;
idx = 0;
V = v, S = s, T = t;
}
void add(int a, int b, flow_t c, flow_t d = 0){
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = d, ne[idx] = h[b], h[b] = idx++;
}
bool bfs(){
for(int i = 0; i <= V; i++) d[i] = -1;
int hh = 0, tt = -1;
q[++tt] = S, d[S] = 0, cur[S] = h[S];
while(hh <= tt){
int t = q[hh++];
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if (d[j] == -1 && f[i]){
d[j] = d[t] + 1;
cur[j] = h[j];
if (j == T) return true;
q[++tt] = j;
}
}
}
return false;
}
flow_t find(int u, flow_t limit){
if (u == T) return limit;
flow_t flow = 0;
// start from cur[u] instead of h[u] <- important
for(int i = cur[u]; ~i && flow < limit; i = ne[i]){
int j = e[i];
cur[u] = i;
if (d[j] == d[u] + 1 && f[i]){
flow_t t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
else f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
flow_t dinic(){
flow_t res = 0, flow;
while(bfs()) while(flow = find(S, INF)) res += flow;
return res;
}
};
MaxFlow<int> flow;
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
vector<string> g(n);
for(int i = 0; i < n; i++) cin >> g[i];
vector<int> a(n), b(n);
int sum1 = 0, sum2 = 0;
for(int i = 0; i < n; i++)
cin >> a[i], sum1 += a[i];
for(int i = 0; i < n; i++)
cin >> b[i], sum2 += b[i];
if (sum1 != sum2){
cout << "No" << '\n';
return 0;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if (g[i][j] == '-'){
sum1 += 1;
sum2 += 1;
a[i] += 1;
b[j] += 1;
}
}
}
int s = 2 * n, t = 2 * n + 1;
flow.init(2 * n + 1, s, t);
for(int i = 0; i < n; i++){
if (a[i] < 0){
cout << "No" << '\n';
return 0;
}
flow.add(s, i, a[i]);
}
for(int i = 0; i < n; i++){
if (b[i] < 0){
cout << "No" << '\n';
return 0;
}
flow.add(i + n, t, b[i]);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
flow.add(i, j + n, 1);
}
}
if (flow.dinic() != sum1){
cout << "No" << '\n';
return 0;
}
vector<vector<int> > ans(n, vector<int>(n));
for(int x = 0; x < n; x++){
for(int i = flow.h[x]; ~i; i = flow.ne[i]){
int j = flow.e[i];
if (j >= n && j < 2 * n && !flow.f[i]){
ans[x][j - n] = 1;
}
}
}
cout << "Yes" << '\n';
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if (g[i][j] == '-'){
ans[i][j] ^= 1;
}
cout << ans[i][j];
}
cout << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 9680kb
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: 7676kb
input:
3 --- -++ +++ -2 -1 0 -2 -1 0
output:
Yes 110 100 000
result:
ok n=3
Test #3:
score: 0
Accepted
time: 2ms
memory: 9568kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 7568kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 9660kb
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: 9752kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010100101011000001000111011010110101110000000101100101100100111110110100010010011 0110011010111101000110010101010101010101010010011100010010000010000010110110101111110010111011101111 0010001101100110111000111101101001111110111001001000011111111010011111001100101011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 19ms
memory: 17948kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 00101010110000011100101110100010100000011111001100101101100011001001001011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...
result:
ok n=500
Test #9:
score: -100
Runtime Error
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...