QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710212#6398. Puzzle: Tapatassei903WA 0ms3632kbC++235.7kb2024-11-04 19:04:522024-11-04 19:04:53

Judging History

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

  • [2024-11-04 19:04:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3632kb
  • [2024-11-04 19:04:52]
  • 提交

answer


#include <bits/stdc++.h>
#include <bits/extc++.h> 
using namespace std;
#define sz(x) (int)(x).size()
#define rep(i, l, r) for (int i = l; i < (r); i++)
#define rrep(i, l, r) for(int i = (int)(r)-1; i >= (int)(l); i--)
#define all(x) begin(x), end(x)

using ll = long long;
using vi = vector<int>;

using pii = pair<int, int>;

struct mf_graph {
    struct edge {
        int from, to;
        ll cap, flow;
    };

    struct nedge {
        int to, rev;
        ll cap;
    };

    int nn;
    vector<pii> pos;
    vector<vector<nedge>> g;

    mf_graph() : nn(0) {} 
    explicit mf_graph(int n) : nn(n), g(n) {}

    int add_edge(int from, int to, ll cap) {
        int m = sz(pos);
        pos.push_back({from, sz(g[from])});
        int frid = sz(g[from]);
        int toid = sz(g[to]);
        if (from == to) toid ++ ;
        g[from].push_back(nedge{to, toid, cap});
        g[to].push_back(nedge{from, frid, 0});
        return m;
    }

    ll flow(int s, int t) {
        return flow(s, t, numeric_limits<ll>::max());
    }

    ll flow(int s, int t, ll flow_limit) {
        vector<int> lv(nn), iter(nn);
        queue<int> q;

        auto bfs = [&]() {
            fill(all(lv), -1);
            lv[s] = 0;
            queue<int>().swap(q);
            q.push(s);
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (auto e : g[v]) {
                    if (e.cap == 0 || lv[e.to] >= 0) continue;
                    lv[e.to] = lv[v] + 1;
                    if (e.to == t) return;
                    q.push(e.to);
                }
            }
        };
        auto dfs = [&](auto self, int v, ll up ) {
            if (v == s) return up;
            ll res = 0;
            int lvvv = lv[v];
            for (int& i = iter[v]; i < sz(g[v]); i ++ ) {
                nedge& e = g[v][i];
                if (lvvv <= lv[e.to] || g[e.to][e.rev].cap == 0)continue;
                ll d = self(self, e.to, min(up - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == up) return res;
            }
            lv[v] = nn;
            return res;
        };

        ll flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (lv[t] == -1) break;
            fill(all(iter), 0);
            ll f = dfs(dfs, t, flow_limit - flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    edge get_edge(int i) {
        int m = int(pos.size());
        auto _e = g[pos[i].first][pos[i].second];
        auto _re = g[_e.to][_e.rev];
        return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
    }

    vector<edge> edges() {
        int m = int(pos.size());
        vector<edge> result;
        for (int i = 0; i < m; i++) {
            result.push_back(get_edge(i));
        }
        return result;
    }

};

vector<int> dx = {1, 1, 1, 0, 0, -1, -1, -1}, dy = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
    std::cin.tie(0)->sync_with_stdio(0);

    int n, m;cin >> n >> m;
    vector<string> s(n*2-1);rep(i, 0, n*2-1)cin >> s[i];

    mf_graph mf(n * m + 2);int S = n * m, T = n * m + 1;
    
    vector<string> ans = s;

    auto get = [&](int u, int v) {
        return s[u*2][v*2] - '0';
    };

    auto place_all = [&](int u, int v) {
        rep(t, 0, 8) {
            int x = u*2 + dx[t], y = v*2 + dy[t];
            if (0 <= x && x < n*2 - 1 && 0 <= y && y < m*2-1)ans[x][y] = '#';
        }
    };

    auto place_down = [&](int u, int v) {
        place_all(u, v);
        place_all(u+1, v);
        ans[u*2+1][v*2] = '.';
    };
    auto place_right = [&](int u, int v) {
        place_all(u, v);
        place_all(u, v+1);
        ans[u*2][v*2+1] = '.';
    };
    auto num = [&](int u, int v) {
        return u * m + v;
    };

    auto connect = [&](int x, int y)->bool{
        if (x > y)swap(x, y);

        if (x == 2 && y == 2) return 1;
        if (x == 2 && y == 4) return 1;
        if (x == 4 && y == 4) return 1;
        if (x == 7 && y == 7) return 1;
        return 0;
    };
    
    int M1 = 0, M2 = 0;

    rep(i, 0, n-1) rep(j, 0, m) {
        if (connect(get(i, j), get(i+1, j))) {
            if ((i+j) % 2)mf.add_edge(num(i, j), num(i+1, j), 1);
            else mf.add_edge(num(i+1, j), num(i, j), 1);
            M1++;
        }
    }
        rep(i, 0, n) rep(j, 0, m-1) {
        if (connect(get(i, j), get(i, j+1))) {
            if ((i+j) % 2)mf.add_edge(num(i, j), num(i, j+1), 1);
            else mf.add_edge(num(i, j+1), num(i, j), 1);
            M2++;
        }
    }

    int N = 0;
    rep(i, 0, n) rep(j, 0, m) {
        if (get(i, j) == 2 || get(i, j) == 4 || get(i, j) == 7) {
            N += 1;
            if ((i+j) % 2) mf.add_edge(S, num(i, j), 1);
            else mf.add_edge(num(i, j), T, 1);
        }
        else {
            place_all(i, j);
        }
    }

    ll flow = mf.flow(S, T);
    // cout << flow << endl;

    rep(i, 0, M1) {
        auto e = mf.get_edge(i);
        if (e.cap) {
            int I = min(e.from, e.to);
            
            place_down(I/m, I%m);
        } 
    }
    rep(i, M1, M1+M2) {
        auto e = mf.get_edge(i);
        if (e.cap) {
            int I = min(e.from, e.to);
            place_right(I/m, I%m);
        } 
    }

    if (N == flow * 2) {
        cout << "YES" << endl;
        for(auto x:ans) {
            cout << x << endl;
        }
    }
    else {
        cout << "NO" << endl;
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3
2.4.3
.....
5.8.5
.....
3.5.3

output:

YES
2.4#3
#####
5#8#5
#####
3#5#3

result:

ok Correct.

Test #2:

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

input:

3 3
3.4.3
.....
5.7.5
.....
3.5.3

output:

NO

result:

ok Correct.

Test #3:

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

input:

2 2
2.2
...
2.2

output:

YES
2.2
###
2.2

result:

ok Correct.

Test #4:

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

input:

2 50
2.4.4.4.4.5.5.5.5.5.5.5.5.4.5.5.4.4.5.5.5.5.4.5.5.5.5.5.4.4.5.4.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.4.5.3
...................................................................................................
2.5.5.4.4.5.5.5.4.4.5.5.5.4.5.5.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.5.4.4.5.5.5.5.4...

output:

YES
2#4#4#4.4#5#5#5#5#5#5#5#5#4#5#5#4.4#5#5#5#5#4#5#5#5#5#5#4.4#5#4#5#5#5#5#5#5#5#5#5#5#5#4.4#5#5#4#5#3
##########################.###################################################################.####
2#5#5#4.4#5#5#5#4.4#5#5#5#4#5#5#5#5#5#5#5#5#4#4.4#5#5#5#5#5#5#4#4.4#5#5#5#5#5#5#5#4.4#5#5#5#5#4#...

result:

wrong answer Clue not satisfied at (1,1)