QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#113158#1943. Bordersckiseki#WA 3ms4856kbC++144.1kb2023-06-16 15:54:342023-06-16 15:54:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-16 15:54:37]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:4856kb
  • [2023-06-16 15:54:34]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int maxn = 105;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int g[maxn][maxn];
int vis[maxn][maxn], cid[maxn][maxn];

void dfs(int i, int j) {
    vis[i][j] = true;
    for (int k = 0; k < 4; k++) {
        if (g[i + dx[k]][j + dy[k]] != g[i][j]) continue;
        if (vis[i + dx[k]][j + dy[k]]) continue;
        cid[i + dx[k]][j + dy[k]] = cid[i][j];
        dfs(i + dx[k], j + dy[k]);
    }
}

int color[maxn * maxn];
vector<int> nei[maxn * maxn];
int isborder[maxn * maxn];

template <typename Cap = int64_t>
class Dinic {
    private:
        struct E {
            int to, rev;
            Cap cap;
        };
        int n, st, ed;
        vector<vector<E>> G;
        vector<int> lv, idx;
        bool BFS() {
            lv.assign(n, -1);
            queue<int> bfs;
            bfs.push(st);
            lv[st] = 0;
            while (not bfs.empty()) {
                int u = bfs.front(); bfs.pop();
                for (auto e: G[u]) {
                    if (e.cap <= 0 or lv[e.to] != -1)
                        continue;
                    bfs.push(e.to);
                    lv[e.to] = lv[u] + 1;
                }
            }
            return lv[ed] != -1;
        }
        Cap DFS(int u, Cap f) {
            if (u == ed) return f;
            Cap ret = 0;
            for (int &i = idx[u]; i < int(G[u].size()); ++i) {
                auto &e = G[u][i];
                if (e.cap <= 0 or lv[e.to] != lv[u] + 1) continue;
                Cap nf = DFS(e.to, min(f, e.cap));
                ret += nf; e.cap -= nf; f -= nf;
                G[e.to][e.rev].cap += nf;
                if (f == 0) return ret;
            }
            if (ret == 0) lv[u] = -1;
            return ret;
        }
    public:
        void init(int n_) { G.assign(n = n_, vector<E>()); }
        void add_edge(int u, int v, Cap c) {
            G[u].push_back({ v, int(G[v].size()), c });
            G[v].push_back({ u, int(G[u].size())-1, 0 });
        }
        Cap max_flow(int st_, int ed_) {
            st = st_, ed = ed_; Cap ret = 0;
            while (BFS()) {
                idx.assign(n, 0);
                Cap f = DFS(st, numeric_limits<Cap>::max());
                ret += f;
                if (f == 0) break;
            }
            return ret;
        }
};

Dinic<int> flow;

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++)
            g[i + 1][j + 1] = s[j];
    }

    int c = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!vis[i][j])
                cid[i][j] = ++c, color[c] = g[i][j], dfs(i, j);
        }
    }

    for (int i = 1; i + 1 <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (cid[i][j] != cid[i + 1][j]) {
                nei[cid[i][j]].emplace_back(cid[i + 1][j]);
                nei[cid[i + 1][j]].emplace_back(cid[i][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j + 1 <= m; j++) {
            if (cid[i][j] != cid[i][j + 1]) {
                nei[cid[i][j]].emplace_back(cid[i][j + 1]);
                nei[cid[i][j + 1]].emplace_back(cid[i][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        isborder[cid[i][1]] = true;
        isborder[cid[i][m]] = true;
    }
    for (int j = 1; j <= m; j++) {
        isborder[cid[1][j]] = true;
        isborder[cid[n][j]] = true;
    }

    flow.init(c + 2);
    int S = 0, T = c + 1;

    for (int i = 1; i <= c; i++) {
        if (color[i] == '0') {
            flow.add_edge(S, i, 1);
            if (isborder[i]) {
                flow.add_edge(i, T, 1e9);
            }
        } else {
            flow.add_edge(i, T, 1);
            if (isborder[i]) {
                flow.add_edge(S, i, 1e9);
            }
        }
    }

    for (int a = 1; a <= n; a++) {
        if (color[a] == '0') {
            for (int b: nei[a]) {
                flow.add_edge(a, b, 1e9);
            }
        }
    }

    int f = flow.max_flow(S, T);
    cout << f << '\n';

    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 4856kb

input:

100 100
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

396

result:

wrong answer 1st lines differ - expected: '5198', found: '396'