QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#798756#9665. Black-White Cubic Latticeucup-team004AC ✓45ms4920kbC++234.0kb2024-12-04 16:47:102024-12-04 16:47:10

Judging History

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

  • [2024-12-04 16:47:10]
  • 评测
  • 测评结果:AC
  • 用时:45ms
  • 内存:4920kb
  • [2024-12-04 16:47:10]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
template<class T>
struct MaxFlow {
    struct _Edge {
        int to;
        T cap;
        _Edge(int to, T cap) : to(to), cap(cap) {}
    };
    int n;
    std::vector<_Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;
    MaxFlow() {}
    MaxFlow(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        e.clear();
        g.assign(n, {});
        cur.resize(n);
        h.resize(n);
    }
    bool bfs(int s, int t) {
        h.assign(n, -1);
        std::queue<int> que;
        h[s] = 0;
        que.push(s);
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (int i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t) {
                        return true;
                    }
                    que.push(v);
                }
            }
        }
        return false;
    }
    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        auto r = f;
        for (int &i = cur[u]; i < int(g[u].size()); ++i) {
            const int j = g[u][i];
            auto [v, c] = e[j];
            if (c > 0 && h[v] == h[u] + 1) {
                auto a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0) {
                    return f;
                }
            }
        }
        return f - r;
    }
    void addEdge(int u, int v, T c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }
    T flow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, std::numeric_limits<T>::max());
        }
        return ans;
    }
    std::vector<bool> minCut() {
        std::vector<bool> c(n);
        for (int i = 0; i < n; i++) {
            c[i] = (h[i] != -1);
        }
        return c;
    }
    struct Edge {
        int from;
        int to;
        T cap;
        T flow;
    };
    std::vector<Edge> edges() {
        std::vector<Edge> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};
constexpr int inf = 1E9;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M, L;
    std::cin >> N >> M >> L;
    
    std::vector s(L, std::vector<std::string>(N));
    std::vector c(L, std::vector(N, std::vector<int>(M)));
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < N; j++) {
            std::cin >> s[i][j];
        }
    }
    MaxFlow<int> g(N * M * L + 2);
    const int S = N * M * L, T = S + 1;
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < M; k++) {
                std::cin >> c[i][j][k];
                if (s[i][j][k] == 'W') {
                    g.addEdge((i * N + j) * M + k, T, c[i][j][k]);
                } else {
                    g.addEdge(S, (i * N + j) * M + k, c[i][j][k]);
                }
                if (i > 0) {
                    g.addEdge((i * N + j) * M + k, ((i - 1) * N + j) * M + k, inf);
                }
                if (j > 0) {
                    g.addEdge((i * N + j) * M + k, (i * N + (j - 1)) * M + k, inf);
                }
                if (k > 0) {
                    g.addEdge((i * N + j) * M + k, (i * N + j) * M + (k - 1), inf);
                }
            }
        }
    }
    g.addEdge(S, 0, inf);
    g.addEdge(N * M * L - 1, T, inf);
    
    int ans = g.flow(S, T);
    std::cout << ans << "\n";
    
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2 2
WW
WW
BB
BB
1 1
1 1
2 2
2 2

output:

5

result:

ok single line: '5'

Test #2:

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

input:

2 1 1
W
B
0
1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 15ms
memory: 4920kb

input:

1 1 5000
B
W
W
W
W
W
W
W
W
B
B
B
W
B
W
B
W
B
W
W
B
W
W
B
B
W
B
B
B
B
W
W
W
W
W
W
W
B
B
B
B
B
B
B
B
B
W
B
B
W
B
B
B
W
W
B
B
W
W
W
W
W
W
W
B
B
B
B
W
B
B
W
B
W
W
W
W
W
B
B
W
B
B
W
W
B
W
B
B
B
B
W
W
W
B
B
W
B
W
W
W
W
W
B
W
B
B
B
W
W
B
W
B
B
W
B
W
B
B
B
B
B
W
B
B
W
W
W
W
B
W
B
W
B
W
B
W
B
B
W
B
B
B
W
W
W...

output:

1218

result:

ok single line: '1218'

Test #4:

score: 0
Accepted
time: 16ms
memory: 4672kb

input:

5000 1 1
B
W
B
W
B
B
B
B
W
W
W
W
B
W
W
W
W
W
W
W
B
B
B
B
B
B
W
W
W
B
B
B
B
B
B
B
W
B
W
B
W
B
B
W
B
B
W
B
B
B
W
B
W
B
B
B
B
W
B
W
W
B
W
B
W
B
W
W
W
W
B
B
W
W
W
B
W
W
W
W
B
W
B
W
B
W
W
W
W
B
B
W
B
W
B
W
B
B
W
W
W
B
B
B
B
W
W
W
B
W
B
W
B
B
B
W
B
W
B
W
B
B
B
W
B
W
B
B
B
W
B
B
B
B
W
W
B
W
B
W
W
W
W
W
B
W...

output:

242900000

result:

ok single line: '242900000'

Test #5:

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

input:

1 5000 1
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

output:

100000

result:

ok single line: '100000'

Test #6:

score: 0
Accepted
time: 42ms
memory: 4088kb

input:

2 2500 1
BWBBWWWBBBWBWBBBBBBBWBBBBBWWWWBBWBWWBBBBBBBBBWBWBWBBWWBBWWWBBWWWBBWWWWBWBBBWWBWBWBWWBBBWBWWWWWWWWWBBBBWWWBBBBWWBWBWBWBWBWWBWBBBBBBWBBWWWBWWBWWBWWBWWWBWWWBBBBBBBWBBWWBWWWWWWWBBBBWWBBBBBWWWBBBBBBWBWWWBWWWWBBBBWWWWWBWWBBBBWWWBWWBBWBWBBWWWBBBWWBBWBBWWBWWBBWBWBBWBWWWBWWWWWBBWWWBWWWWWWBWWWBBBWWBW...

output:

12335546

result:

ok single line: '12335546'

Test #7:

score: 0
Accepted
time: 39ms
memory: 4256kb

input:

1666 3 1
WBB
WWB
BWB
BWW
WWB
WWB
BBB
BBB
BBW
WBB
BBB
BBW
BWW
WWB
BBB
BBW
WWW
BBW
WWW
BWW
BWB
WWB
BWB
WWW
BWB
BWW
WWB
BWW
BWB
BBB
BBW
BBB
BWB
WWB
WBW
WWB
BWB
BWW
BWB
WWW
BBW
BBW
BBW
BWW
BWB
BBB
WWB
BBB
BBB
WBB
BBW
BBB
BBW
BBB
BBB
WBW
BBW
WBW
BBB
BWB
WBW
BBW
WWW
WWW
WWW
BWB
WWB
BBW
WBB
WWB
BWW
BBW
WBW...

output:

11971988

result:

ok single line: '11971988'

Test #8:

score: 0
Accepted
time: 45ms
memory: 4628kb

input:

4 1 1250
W
B
W
B
B
W
B
B
B
W
B
B
W
W
W
W
B
B
B
B
W
B
B
B
B
W
W
B
W
W
B
W
W
B
W
W
B
B
W
B
B
W
B
B
W
B
W
W
B
W
W
B
W
B
W
B
W
W
W
B
B
B
W
W
B
B
W
B
B
B
W
B
B
W
W
W
B
B
W
B
W
B
B
B
W
B
B
W
B
W
B
B
B
B
B
W
W
W
B
W
B
W
W
W
W
B
W
B
W
B
B
B
W
W
B
W
W
W
W
W
B
B
B
B
B
W
W
W
W
B
B
W
W
W
W
W
B
B
B
B
B
B
W
W
W
B...

output:

12131611

result:

ok single line: '12131611'

Test #9:

score: 0
Accepted
time: 8ms
memory: 4112kb

input:

70 71 1
WBBWBBBWWBBBWWWBBBWWBWWWBWBBBWBWWWWWBWWBBWBWWWBWBWWBBWWBBWWBBBWBWWWWWWB
WWBBBWWBWWBWBBWBBWWWWBBBWWWBBWWBBWWWWWBWWWBWWBWWBWBWWBBWWBBWBWWBWBWBBWW
BWWWBWBBBBWWWWWWBWWBBWWBWWWWWBWWWWBBWBBWBWBWWBWWBBBBWBBBBWBBWWWWBBBBWWB
BWBWBWBBWWWBBWWBBWWBWWBBWWBWBBWBWBBWBWWBWWBBBWBWWWBBWBBBWWWBBWBBBWWWBBW
WWWW...

output:

11904642

result:

ok single line: '11904642'

Test #10:

score: 0
Accepted
time: 17ms
memory: 4380kb

input:

12 4 95
BBWW
WBWW
BWBW
WWBW
BWBB
BWBW
WBWW
BWWB
WWBW
BWBW
WWWB
BWBW
WWWB
WBWB
BWBB
BBBW
WBBB
BWWW
BWWW
BBWW
WWBW
WBWB
WWBB
WWWW
WBWW
BBBW
WBBB
WWWW
WBBW
BBBB
WWBB
WBWW
WWWW
BBWW
WBBW
WWBW
WWWB
WWWB
BWWW
BWWW
BWWB
BWBW
BBBB
WWWB
WBBB
WWWB
WWWW
WBWB
WWWB
BBBB
WWBB
WBBW
BBWB
BBWB
WWWW
WWBW
WBWW
WBWW
WW...

output:

10402

result:

ok single line: '10402'

Test #11:

score: 0
Accepted
time: 8ms
memory: 4376kb

input:

25 10 20
BBWBWBWBBW
BBBWBBWBWW
WBWBWBWWWB
WBWBBWBWBW
WWWWWWWBWB
BBWBWBWWBB
BBBBBWBWWB
BWWWWBWWBW
BWBBBBWWWW
WWBBWBWBWW
WWBWWWBBWW
BWBWWBBWBB
BBWBBWBWWB
WBBBBBWWWW
BBWWBBBWWB
WWWWBWWWWB
WBBBWWBWBW
WBBWBWWBBB
BBWBWWBBWW
WWBWBWBWWB
BBBBWWBWBB
WWWWWWBBWB
WWWBWWBBBW
WBBWWWWBWW
BBBWWWBWWB
BWWWBWBBBB
BBBWW...

output:

11106

result:

ok single line: '11106'

Test #12:

score: 0
Accepted
time: 11ms
memory: 4404kb

input:

50 2 50
BB
WB
BB
BB
BB
BW
BW
WW
BB
WB
WW
BW
WB
BB
BW
WW
BW
BW
BB
WB
WB
BW
WB
WB
WW
WW
WB
BB
WW
BW
WB
BW
WW
BB
BW
BB
BW
BB
WB
WW
WW
WW
BB
WW
BW
BB
BB
BB
BB
WB
BW
WW
WB
BW
BW
BW
WW
WB
BB
WW
WW
BB
WW
BB
WB
BB
BW
BB
BB
WB
WW
BB
WW
WB
WB
WW
WW
BB
BW
WB
WB
WW
WB
WB
WB
WB
BB
WB
WW
BW
WW
BB
WB
BW
BW
WB
WB
W...

output:

11686

result:

ok single line: '11686'

Test #13:

score: 0
Accepted
time: 33ms
memory: 4076kb

input:

4 5 210
BWBWW
BBBWW
WBWWW
WBWWW
WBWBB
BWBWW
BBBWB
WBBWB
BWWWB
BWBBB
BWBBB
WBBBB
BBBBB
WWBWB
WBBBW
WBWWB
WBBBB
BBWBB
BWWBB
WBBWW
WWWBW
WBBBW
WWBBB
WWBBB
WWBWB
BWBWW
BWBBB
BWWBB
BBWBB
BWWWB
WWBBW
WBBBB
WBWBW
BBWBW
WBBBB
BWBWW
BBBWW
BBWWW
WWBBB
WWWWB
WWWBB
BBBWB
WWBWB
BBWBW
BBBBB
BBBBB
WWWWW
BBWBB
WWBW...

output:

9895

result:

ok single line: '9895'

Test #14:

score: 0
Accepted
time: 11ms
memory: 4168kb

input:

15 43 7
BWWWWBWBWBBBWWWWWBWBWBBBBBWWBBBBWWBWBWWBWBW
BBWBWBWBBBWBBWWWWBWWWWWWBBBBBWWBWBWWWBBBWWB
BWBBWBBBBBWBBWBBBWBBBBBBBWBBBBBWWWWBBBBBBBW
BWBWWBBWBWBBBBWBBWBWWWWWWWBBWBWWBWBBWBBWBBB
BBWWWBWWWBWWBWWBBWWWWWWWWBBWWWWWWBWBBBWWWBB
WBWWBWBWBWWBWWWWWWWWBWWWBWWWWWBWWBBWBBBBWBW
BBBBWWWBBWBBBBBBWWWBWBWWBBWW...

output:

10218

result:

ok single line: '10218'

Test #15:

score: 0
Accepted
time: 18ms
memory: 4384kb

input:

10 10 50
BBBBWWBBWW
BWBBWBWWBB
WWBBWWWWBB
WBWWBBWWBW
WBWBWBWBWW
BBWBWWBWBB
BWBWBBWBBB
WWWBWBBBBW
WBWWBBWWBW
BWWWWBBWBB
WWWWBWWWBW
BBWBWWWBWB
WWWWWWWBBB
WBBBWWWWBB
WWWBWBBBBW
BWWWBWWWBB
WWBBBBBBWB
BWBBWBWWWB
BBWWWWWWWB
WWBWWBBWWW
BWWWBWWBBB
WWBBWWWBBB
WWWBWWBWWW
BWBWWBBWBW
BBBBBWBWBW
WBWWWWWBBB
BBBBB...

output:

113532736

result:

ok single line: '113532736'

Test #16:

score: 0
Accepted
time: 10ms
memory: 4384kb

input:

16 17 18
WBWBWBWBWWWWBBWBB
BBWBBWWWWBWBWBBBW
BBWBWBBBBBWBWWBWB
WBBBBBWWBBBBBWWBB
WBBWWWWBWBWBWWWBW
WBBWWWWWWBWWBWWBW
WWBBBBBBBWWBBWBWB
WWBWBWWWBWWWWBWBW
BBBBBBBBBBWWWBBBW
WWBBWBWBBWBBWBWWW
WBBWBBBBBBWWWWWBW
BBBBWWBBWBBBBBBBB
WBWWBWWWBBWWWBWBW
WBBWBBBBWBWBWBBWB
WBBBWBWBWBBBWWWWB
WWBWBWWWWBWWBWBWB
WWB...

output:

109472675

result:

ok single line: '109472675'

Test #17:

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

input:

17 17 17
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBB...

output:

100000

result:

ok single line: '100000'

Test #18:

score: 0
Accepted
time: 6ms
memory: 4344kb

input:

17 17 17
WWWBBBBWWBBBWWBWW
WWWWBBBBBWBBBBBWW
BWWWBBWWBWBWBWWWW
WBBBBWBWWBWBWWWWB
BWWBWWWWWBWBBBBWW
WBBBWWBBBBWBBBWWB
BWWWBBBBWWBWBWBWW
WWBWBWBBBBWBWBBBW
WWBWWWBWBBWBWWWBW
BWWBBWWBBBWBWBWWB
BBBWBBBWWBWBWBWWB
WWWBWWWBBWBBWWWBB
WBBBWBWBBBWWWBBBW
WBWBWBBBWBWBBWWWW
BBBWWBWWBWWBWBBBB
WBBBWBBWBBWBBBWBB
WWW...

output:

1128

result:

ok single line: '1128'

Test #19:

score: 0
Accepted
time: 7ms
memory: 4096kb

input:

17 17 17
WWWBBWWBBWBWWBWWB
BWWBBBWWWWWWWBWBB
WWWBWBBBBBWWWWWBB
WWWWWWBWBBBBWWWBW
WBWWBBWWWBBWBWWWB
BWBBWWWBBWWWBBBBW
WBBBBWBWWWBWWWBBB
WWWWWWWWBBWWWWWBW
WWWWBBWBWWWWWBWWB
BBBBBBWWBBBWBBBWW
BBBBBBBBBWWWWWWWB
BBWWWWBBWWBBWWBBB
WBWBBBBWWBWBBWWBB
BBBBWBWWWBBBBBBWB
BWBWWWBBWWBBWBWBB
BBWWWBWWBWBWWBWBB
WBB...

output:

5346

result:

ok single line: '5346'

Test #20:

score: 0
Accepted
time: 13ms
memory: 4136kb

input:

17 17 17
WWBBWWWWWBWWWBBBW
BWWWWWWBWBWWBBWWW
WWWWWBWBWBWWWWWBW
WWWWBWBBBBWBWWWWW
BBBBWBBWWWWWBWWWW
WBWWBWWWBBBBBWBBW
BBWWWWWBWBBBBWBBW
BWWBBBWBWWWBBWWBW
WWBBWWWBBWWBBWBWB
WBBBWBWBBBBBBBBWW
BWWBWBBWBWWBWBBBB
WWWBWWWWWBWBBWWWW
BBBBBBWBWWWBWBBBB
WWWWWBBBBBBWWWWWB
BWBBWWWBWBBWWBBWB
WBWBBBBBWBWBWWBBB
WWW...

output:

113499454

result:

ok single line: '113499454'

Extra Test:

score: 0
Extra Test Passed