QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#729085#7857. (-1,1)-SumpletenekoyellowTL 20ms12184kbC++232.9kb2024-11-09 16:28:122024-11-09 16:28:15

Judging History

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

  • [2024-11-09 16:28:15]
  • 评测
  • 测评结果:TL
  • 用时:20ms
  • 内存:12184kb
  • [2024-11-09 16:28:12]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char nl = '\n';

class MF {
  public:
    MF(int _n, int _s, int _t): n(_n), s(_s), t(_t) {
        head.assign(n, -1); dep.resize(n);
    }
    void addedge(int u, int v, int w) {
        e.push_back({v, head[u], w, 0}); head[u] = e.size()-1;
        e.push_back({u, head[v], 0, 0}); head[v] = e.size()-1;
    }
    ll dinic() {
        ll maxflow = 0;
        while (bfs()) cur = head, maxflow += dfs(s, inf);
        return maxflow;
    }

    static const int inf = numeric_limits<int>::max();
    int n, s, t;
    struct Edge { int v, nxt, c, f; };
    vector<Edge> e; vector<int> head;
    vector<int> dep, cur;
    bool bfs() {
        queue<int> q; q.push(s);
        fill(dep.begin(), dep.end(), 0); dep[s] = 1;
        while (q.size()) {
            int u = q.front(); q.pop();
            for (int i = head[u]; ~i; i = e[i].nxt) {
                int v = e[i].v;
                if (!dep[v] && e[i].c > e[i].f) q.push(v), dep[v] = dep[u]+1;
            }
        }
        return dep[t];
    }
    int dfs(int u, int flow) {
        if (u == t || !flow) return flow;
        int ret = 0;
        for (int &i = cur[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            if (dep[v] == dep[u]+1) {
                int d = dfs(v, min(flow-ret, e[i].c-e[i].f));
                if (!d) continue;
                e[i].f += d, e[i^1].f -= d; ret += d;
                if (ret == flow) break;
            }
        }
        return ret;
    }
};

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vector<string> g(n);
    for (auto &s: g)
        cin >> s;
    vector<int> r(n), c(n);
    for (auto &e: r)
        cin >> e;
    for (auto &e: c)
        cin >> e;

    if (n == 1 && r[0] != c[0]) {
        cout << "No\n";
        return 0;
    }

    int s = 2*n, t = 2*n+1;
    MF mf(t+1, s, t);
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (r[i] > 0) ans += r[i];
        r[i] >= 0 ? mf.addedge(s, i, r[i]) : mf.addedge(i, t, -r[i]);
        for (int j = 0; j < n; j++) {
            g[i][j] == '+' ? mf.addedge(i, n+j, 1) : mf.addedge(n+j, i, 1);
        }
    }
    for (int j = 0; j < n; j++) {
        if (c[j] < 0) ans -= c[j];
        c[j] >= 0 ? mf.addedge(n+j, t, c[j]) : mf.addedge(s, n+j, -c[j]);
    }

    ll maxflow = mf.dinic();
    if (ans != maxflow) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
        vector<string> a(n, string(n, '0'));
        for (int i = 0; i < n; i++) {
            for (auto k = mf.head[i]; ~k; k = mf.e[k].nxt) {
                int j = mf.e[k].v;
                if (j == s || j == t) continue;
                if (mf.e[k].f) a[i][j-n] = '1';
            }
        }
        for (auto &s: a)
            cout << s << '\n';
    }

    return 0;
}

详细

Test #1:

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

input:

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

output:

Yes
001
001
111

result:

ok n=3

Test #2:

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

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

input:

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

output:

No

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

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

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

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

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

input:

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

output:

Yes
1111010100111111010010011010100010100000000000000000000000000000000000000000000011110110100010010011
0110011010111101000110101010100010100000000000000000000000000000000000000000101111110010111011101111
0010001101100110111000000010010010000000000000000000000000000000000000000000001011100010011101...

result:

ok n=100

Test #8:

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

input:

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

output:

Yes
11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001010001001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok n=500

Test #9:

score: -100
Time Limit Exceeded

input:

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

output:


result: