QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291942#7857. (-1,1)-Sumpleteucup-team045#TL 2775ms461992kbC++203.9kb2023-12-27 14:25:512023-12-27 14:25:51

Judging History

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

  • [2023-12-27 14:25:51]
  • 评测
  • 测评结果:TL
  • 用时:2775ms
  • 内存:461992kb
  • [2023-12-27 14:25:51]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<limits>
using namespace std;
using LL = long long;

const int maxn = 1e5 + 5, maxm = 3.5e7 + 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: 9948kb

input:

3
+-+
-++
+-+
1 1 1
1 -1 3

output:

Yes
111
001
001

result:

ok n=3

Test #2:

score: 0
Accepted
time: 2ms
memory: 9796kb

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: 7724kb

input:

3
+-+
-++
++-
1 0 2
2 2 -1

output:

No

result:

ok n=3

Test #4:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

score: 0
Accepted
time: 1ms
memory: 7908kb

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

score: 0
Accepted
time: 0ms
memory: 9936kb

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: 0ms
memory: 8060kb

input:

100
++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++
-++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++
--+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...

output:

Yes
1111010100111111010010100101011000001000111011010110101110000000101100101100100111110110100010010011
0110011010111101000110010101010101010101010010011100010010000010000010110110101111110010111011101111
0010001101100110111000111101101001111110111001001000011111111010011111001100101011100010011101...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 11ms
memory: 15248kb

input:

500
--+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...

output:

Yes
00101010110000011100101110100010100000011111001100101101100011001001001011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...

result:

ok n=500

Test #9:

score: 0
Accepted
time: 2456ms
memory: 460828kb

input:

4000
-++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...

output:

Yes
01101010100101111000101100000011000101110011100111111100010110111111100001000111011001100010110010000100010011010101000001010001001000100011101111010000011001101101011010011101001001010000111011111011101010001110110100101001100111100010100110001010001000111010000101001100010000010100100001111101...

result:

ok n=4000

Test #10:

score: 0
Accepted
time: 2342ms
memory: 459744kb

input:

4000
+---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...

output:

Yes
10001001101001101011001110011001110101010011111101101011101000111101011100001101000110011001110000011000110100111100001100110010101100100111110100011101110011110111111110100001010100010011011101101101110100011111110011001010001100000000101001100001011010110001001100100001011101001101111011000011...

result:

ok n=4000

Test #11:

score: 0
Accepted
time: 2463ms
memory: 461188kb

input:

4000
-+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...

output:

Yes
01001000000100111011000001100101101101101010111111001100101101011100011010111110111111010110110110101100010100000001101110110101111011010100000100001001000011110000000110100111000011111110100101000101111101000001100000001111001010110001111011110110111010110001001000101111110011000101111110101000...

result:

ok n=4000

Test #12:

score: 0
Accepted
time: 2339ms
memory: 461992kb

input:

4000
+-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...

output:

Yes
10100000111100000111101011010000111000110010001110101100000010101111000010111100101100001010001001000001011001101110001000111000110111000111100011000011100100010001110110101010011100110000110100000011101101100100111000100000001111010110011010010000001111100010001101111011101111010001101111000011...

result:

ok n=4000

Test #13:

score: 0
Accepted
time: 2375ms
memory: 460628kb

input:

4000
-+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...

output:

Yes
01110001000000010111101110110100110000111111000100011011110111011110100010011100000101001101001011110010011010001111111110111111101110010100011010110000101100110111111111111110111011011101101100010001110101111111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...

result:

ok n=4000

Test #14:

score: 0
Accepted
time: 2100ms
memory: 461112kb

input:

4000
+--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...

output:

Yes
10011111001100101110110101010100110000001111000111010100100000011010011010111000001011111010000001111011110101100000011001111101010010111111111111111011010101000100011111011001000011100101110101110100110001011110101011011011011100100110101100111111110011111110101100100001111111111100011000010010...

result:

ok n=4000

Test #15:

score: 0
Accepted
time: 2775ms
memory: 461728kb

input:

4000
---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...

output:

Yes
00011011010100001101111000000000001110011110110110010100100101011110011011001111100110010100001010001101110100101111111101100011110100101110001010010010100100111111010001111110111100001010101100100010010111001111110111010001001000000000001101110011111110011011111001110101111111110010001110010100...

result:

ok n=4000

Test #16:

score: -100
Time Limit Exceeded

input:

4000
++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...

output:


result: