QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291941#7857. (-1,1)-Sumpleteucup-team045#RE 19ms17948kbC++203.9kb2023-12-27 14:25:002023-12-27 14:25:00

Judging History

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

  • [2023-12-27 14:25:00]
  • 评测
  • 测评结果:RE
  • 用时:19ms
  • 内存:17948kb
  • [2023-12-27 14:25:00]
  • 提交

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

output:


result: