QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#289707#7857. (-1,1)-Sumpleteucup-team296#TL 2176ms650164kbC++143.7kb2023-12-23 21:28:502023-12-23 21:28:50

Judging History

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

  • [2023-12-23 21:28:50]
  • 评测
  • 测评结果:TL
  • 用时:2176ms
  • 内存:650164kb
  • [2023-12-23 21:28:50]
  • 提交

answer

#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

struct maxflow {
    struct edge {
        int src, dst, cap, flw;
    };

    vector<edge> edges;
    vector<vector<int>> graph;
    vector<int> first;
    vector<int> dist;

    maxflow(int n) {
        graph.resize(n);
    }

    void bfs(int s) {
        dist.assign(graph.size(), -1);
        dist[s] = 0;
        int h = 0;
        vector<int> q;
        q.push_back(s);
        while (h < q.size()) {
            int x = q[h++];
            for (int i = 0; i < graph[x].size(); i++) {
                edge& e = edges[graph[x][i]];
                if (e.flw == e.cap) continue;
                int y = e.dst;
                if (dist[y] == -1) {
                    dist[y] = dist[x] + 1;
                    q.push_back(y);
                }
            }
        }
    }

    int dfs(int x, int t, int f) {
        if (f == 0) return 0;
        if (x == t) return f;
        for (int i = first[x]; i < graph[x].size(); i++) {
            first[x] = i;
            edge& e = edges[graph[x][i]];
            edge& er = edges[graph[x][i] ^ 1];
            if (e.flw == e.cap || dist[e.dst] != dist[e.src] + 1)
                continue;
            int y = e.dst;
            int res = dfs(y, t, std::min(f, e.cap - e.flw));
            if (res > 0) {
                e.flw += res;
                er.flw -= res;
                return res;
            }
        }
        return 0;
    }

    long maxFlow(int s, int t) {
        long flow = 0;
        while (true) {
            bfs(s);
            first.assign(graph.size(), 0);
            if (dist[t] == -1) break;
            while (true) {
                int pushed = dfs(s, t, INT_MAX);
                if (pushed > 0) {
                    flow += pushed;
                } else {
                    break;
                }
            }
        }
        return flow;
    }

    void addEdge(int u, int v, int cap) {
        //    cout << u << " " << v << "\n";
        edges.push_back({u, v, cap, 0});
        edges.push_back({v, u, 0, 0});
        graph[u].push_back(edges.size() - 2);
        graph[v].push_back(edges.size() - 1);
    }
};


int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) cin >> r[i];
    for (int i = 0; i < n; i++) cin >> c[i];

    maxflow mf(2 * n + 2);
    int s = 2 * n;
    int t = 2 * n + 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == '+') {
                mf.addEdge(i, n + j, 1);
            } else {
                mf.addEdge(n + j, i, 1);
            }
        }
    }
    int ff = 0;
    for (int i = 0; i < n; i++) {
        ff += abs(r[i]);
        if (r[i] > 0) {
            mf.addEdge(s, i, r[i]);
        } else {
            mf.addEdge(i, t, -r[i]);
        }
    }
    for (int i = 0; i < n; i++) {
        ff += abs(c[i]);
        if (c[i] < 0) {
            mf.addEdge(s, n + i, -c[i]);
        } else {
            mf.addEdge(n + i, t, c[i]);
        }
    }
    int f = mf.maxFlow(s, t);
    if (f * 2 != ff) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int k = i * n + j;
                if (mf.edges[k * 2].flw) {
                    cout << '1';
                } else {
                    cout << '0';
                }
            }
            cout << "\n";
        }
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3452kb

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

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

input:

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

output:

No

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

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

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

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

input:

20
+-------+-----+++-++
-+-++++----++-++-++-
-+++--+---+--+-++---
-+++-+--+----++---+-
+++-+-++++++-+-+---+
-++-----+----++++++-
+-++--+++++-++-+----
+-+----+---+-+++--+-
+++++-+++++----+--+-
------++++---+--++--
++++--------++++--+-
-+-+-++++-+-++-++--+
---+-++---+-++-++---
+-++++-++----+-+++--
+-+...

output:

Yes
01010001010000101110
00000000010010110010
10000100010001001100
10000011010001000111
11100000100001010000
10000000000000001001
01000000000101000100
01000010000000100110
00000000000000000000
10000000001100000001
00000001011100000101
00000000100000000000
00000000000011000000
00000000000001011000
00...

result:

ok n=20

Test #7:

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

input:

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

output:

Yes
0100101011100001011000011010100111110111000101010110000000000000000100001100100111110010100010010011
1001100101000100001010101010101010101001010010011100010010000010000010110110101111110010111011101111
1101110010111011001000000010010110000001000001001000011111110010000110001100101001100010011101...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 20ms
memory: 13488kb

input:

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

output:

Yes
00101010110000011100101110100010100000001110011111101001100101011101111101110010100001101100011101100010011011011100111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100010000000...

result:

ok n=500

Test #9:

score: 0
Accepted
time: 1638ms
memory: 649948kb

input:

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

output:

Yes
00000000100001000000100000000010000001010010000100001000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok n=4000

Test #10:

score: 0
Accepted
time: 1674ms
memory: 649936kb

input:

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

output:

Yes
10001001101001101011001110011001110101010011111101101011101000111101011100001101000110011001110000011000110100111100001100110010101100100111110100011101110011110110111111100001110000010011011101101101110100111111010011001010001100000000101001100001011010110001001100101001011101001001111011000010...

result:

ok n=4000

Test #11:

score: 0
Accepted
time: 1723ms
memory: 650164kb

input:

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

output:

Yes
10110111111011000100111110011010010010010101000000110011010010100011100101000001000000101001001001010011101011111110010001001010000100101011111011110110111100001111111001011000111100000001011010111010000010111110011111110000110101001110000100001001000101001110110111010000001100111010000001010111...

result:

ok n=4000

Test #12:

score: 0
Accepted
time: 1589ms
memory: 649908kb

input:

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

output:

Yes
10100000111100000111101011010000111000110010001110101100000010101111000010111100101100001010001001000001011001101110001000111000110111000111100011000011100100010001110110101010011100110000110100000000000011001110010101101111110000101100100100111111110000011101110010010101010000100110110000111000...

result:

ok n=4000

Test #13:

score: 0
Accepted
time: 1654ms
memory: 649984kb

input:

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

output:

Yes
10001110111111101000010001001011001111000000111011100100001000100001011101100011111010110010110100001101100101110000000001000000010001101011100101001111010011001000000000000001000100100010010011101110001010001111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...

result:

ok n=4000

Test #14:

score: 0
Accepted
time: 2176ms
memory: 650068kb

input:

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

output:

Yes
01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010000000101100110000100101010011101101110111100101000110110110101010001010011...

result:

ok n=4000

Test #15:

score: 0
Accepted
time: 2124ms
memory: 650116kb

input:

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

output:

Yes
11011000110110100011111010000010000100010101010111111010110000010011111100001101100100110000001011000111100101101011011101101000011000001100001100000111001111100100000111000111100000101101100001001001010001001000110011011001001101110001001010001101111111001000110000110101001010111110000100111010...

result:

ok n=4000

Test #16:

score: -100
Time Limit Exceeded

input:

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

output:


result: