QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#729076#7857. (-1,1)-SumpleteKobicGendTL 1716ms513520kbC++233.5kb2024-11-09 16:27:202024-11-09 16:27:20

Judging History

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

  • [2024-11-09 16:27:20]
  • 评测
  • 测评结果:TL
  • 用时:1716ms
  • 内存:513520kb
  • [2024-11-09 16:27:20]
  • 提交

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 sums = 0, sumt = 0;

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

    for(int j = 1; j <= n; j++){
        int tmp;
        cin >> tmp;
        if(tmp > 0) {
            sumt += tmp;
            maxflow.add(j + n, t, tmp);
        } else if (tmp < 0) {
            sums -= 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 == sums && sums == sumt) {
        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;
}

詳細信息

Test #1:

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

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

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

input:

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

output:

No

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

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

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

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

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: 1ms
memory: 3992kb

input:

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

output:

Yes
0100101011100001011000011010100111110111000101010110000000000000000100001100100111110010100010010011
1001100101000100001010101010101010101001010010011100010010000010000010110110101111110010111011101111
1101110010111011001000000010010110000001000001001000011111110010000110001100101001100010011101...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 24ms
memory: 11252kb

input:

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

output:

Yes
00101010110000011100101110100010100000001110011111101001100101011101111101110010100001101100011101100010011011011100111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100010000000...

result:

ok n=500

Test #9:

score: 0
Accepted
time: 1212ms
memory: 513396kb

input:

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

output:

Yes
00000000100001000000100000000010000001010010000100001000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok n=4000

Test #10:

score: 0
Accepted
time: 1325ms
memory: 513448kb

input:

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

output:

Yes
10001001101001101011001110011001110101010011111101101011101000111101011100001101000110011001110000011000110100111100001100110010101100100111110100011101110011110110111111100001110000010011011101101101110100111111010011001010001100000000101001100001011010110001001100101001011101001001111011000010...

result:

ok n=4000

Test #11:

score: 0
Accepted
time: 1373ms
memory: 513424kb

input:

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

output:

Yes
10110111111011000100111110011010010010010101000000110011010010100011100101000001000000101001001001010011101011111110010001001010000100101011111011110110111100001111111001011000111100000001011010111010000010111110011111110000110101001110000100001001000101001110110111010000001100111010000001010111...

result:

ok n=4000

Test #12:

score: 0
Accepted
time: 1277ms
memory: 513520kb

input:

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

output:

Yes
10100000111100000111101011010000111000110010001110101100000010101111000010111100101100001010001001000001011001101110001000111000110111000111100011000011100100010001110110101010011100110000110100000000000011001110010101101111110000101100100100111111110000011101110010010101010000100110110000111000...

result:

ok n=4000

Test #13:

score: 0
Accepted
time: 1259ms
memory: 513444kb

input:

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

output:

Yes
10001110111111101000010001001011001111000000111011100100001000100001011101100011111010110010110100001101100101110000000001000000010001101011100101001111010011001000000000000001000100100010010011101110001010001111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...

result:

ok n=4000

Test #14:

score: 0
Accepted
time: 1716ms
memory: 513496kb

input:

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

output:

Yes
01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010000000101100110000100101010011101101110111100101000110110110101010001010011...

result:

ok n=4000

Test #15:

score: 0
Accepted
time: 1681ms
memory: 513380kb

input:

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

output:

Yes
11011000110110100011111010000010000100010101010111111010110000010011111100001101100100110000001011000111100101101011011101101000011000001100001100000111001111100100000111000111100000101101100001001001010001001000110011011001001101110001001010001101111111001000110000110101001010111110000100111010...

result:

ok n=4000

Test #16:

score: -100
Time Limit Exceeded

input:

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

output:


result: