QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#729011#7857. (-1,1)-SumpletenekoyellowWA 1ms3856kbC++232.8kb2024-11-09 16:21:172024-11-09 16:21:18

Judging History

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

  • [2024-11-09 16:21:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3856kb
  • [2024-11-09 16:21:17]
  • 提交

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;

    int s = 2*n, t = 2*n+1;
    MF mf(t+1, s, t);
    int 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]);
    }
    if (ans != mf.dinic()) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
        vector<string> ans(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) ans[i][j-n] = '1';
            }
        }
        for (auto &s: ans)
            cout << s << '\n';
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

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

output:

No

result:

ok n=3

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3856kb

input:

1
-
-1
1

output:

Yes
0

result:

wrong answer wrong sum at row 1