QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#729046#7857. (-1,1)-SumpleteKobicGendWA 1ms3856kbC++233.4kb2024-11-09 16:25:112024-11-09 16:25:19

Judging History

This is the latest submission verdict.

  • [2024-11-09 16:25:19]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3856kb
  • [2024-11-09 16:25:11]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n'

struct MaxFlow {
    vector<vector<array<int, 3>>> E;
    vector<int> level, curr;

    MaxFlow(int n): E(n), level(n), curr(n) {}

    void add(int u, int v, int w) {
        E[u].push_back({ w, v, int(E[v].size()) });
        E[v].push_back({ 0, u, int(E[u].size()) - 1 });
    }

    bool bfs(int s, int t) {
        queue<int> q;
        fill(level.begin(), level.end(), 0);
        fill(curr.begin(), curr.end(), 0);

        level[s] = 1;
        q.push(s);
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto& [w, v, id] : E[u]) {
                if (w && !level[v]) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[t] > 0;
    }

    int dfs(int u, int t, int maxf) {
        if (u == t) return maxf;
        for (int& i = curr[u]; i < E[u].size(); i++) {
            auto& [w, v, id] = E[u][i];
            if (w && (level[v] == level[u] + 1)) {
                int f = dfs(v, t, min(maxf, w));
                if (f) {
                    w -= f;
                    E[v][id][0] += f;
                    curr[u] = i;
                    return f;
                }
            }
        }
        return 0;
    }

    int dinic(int s, int t) {
        int ans = 0;
        while (bfs(s, t)) {
            while (int f = dfs(s, t, 1e9)) {
                ans += f;
            }
        }
        return ans;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n;
    MaxFlow maxflow(2 * n + 5);
    vector num(n + 2, vector<int>(n + 2));
    int s = 2 * n + 2;
    int t = s + 1;


    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            char x;
            cin >> x;
            if(x == '+') {
                num[i][j] = 1;
                maxflow.add(i, j + n, 1);
            } else {
                maxflow.add(j + n, i, 1);
            }
        }
    }

    ll sum = 0;

    for(int i = 1; i <= n; i++){
        int tmp;
        cin >> tmp;
        if(tmp > 0) {
            maxflow.add(s, i, tmp);
            sum += tmp;
        } else if (tmp < 0) {
            maxflow.add(i, t, -tmp);
        }
    }

    for(int j = 1; j <= n; j++){
        int tmp;
        cin >> tmp;
        if(tmp > 0) {
            maxflow.add(j + n, t, tmp);
        } else if (tmp < 0) {
            sum -= tmp;
            maxflow.add(s, j + n, -tmp);
        }
    }



    vector ans(n + 2, vector<int>(n + 2));
    ll flow = maxflow.dinic(s, t);
    //cerr << "flow == " << flow << endl;
    if (flow == sum) {
        cout << "Yes" << endl;
        for (int u = 1; u <= n; u++){
            for (auto& [w, v, id] : maxflow.E[u]){
                if(v >= (n + 1) && v <= (2 * n) && w != num[u][v - n]) {
                    //cerr << "u == " << u << " v == " << v << " w == " << w << endl;
                    ans[u][v - n] = 1;
                }
            }
        }
        
        for (int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cout << ans[i][j];
            }
            cout << endl;
        }
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

Yes
111
001
001

result:

ok n=3

Test #2:

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

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

input:

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

output:

No

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

Yes
0

result:

wrong answer wrong sum at row 1