QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408402#6398. Puzzle: TapaRico64RE 0ms3520kbC++234.6kb2024-05-10 10:00:252024-05-10 10:00:26

Judging History

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

  • [2024-05-10 10:00:26]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3520kb
  • [2024-05-10 10:00:25]
  • 提交

answer

#include <iostream>
#include <vector>
#include <map>

const int dx[] {-1, 0, 0, 1};
const int dy[] {0, -1, 1, 0};

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

bool dfs(int a, int L, vector<vi>& g, vi& btoa, vi& A, vi& B) {
    if (A[a] != L) return 0;
    A[a] = -1;
    for (int b : g[a]) if (B[b] == L + 1) {
            B[b] = 0;
            if (btoa[b] == -1 || dfs(btoa[b], L + 1, g, btoa, A, B))
                return btoa[b] = a, 1;
        }
    return 0;
}

int hopcroftKarp(vector<vi>& g, vi& btoa) {
    int res = 0;
    vi A(g.size()), B(btoa.size()), cur, next;
    for (;;) {
        fill(all(A), 0);
        fill(all(B), 0);
        /// Find the starting nodes for BFS (i.e. layer 0).
        cur.clear();
        for (int a : btoa) if(a != -1) A[a] = -1;
        rep(a,0,sz(g)) if(A[a] == 0) cur.push_back(a);
        /// Find all layers using bfs.
        for (int lay = 1;; lay++) {
            bool islast = 0;
            next.clear();
            for (int a : cur) for (int b : g[a]) {
                    if (btoa[b] == -1) {
                        B[b] = lay;
                        islast = 1;
                    }
                    else if (btoa[b] != a && !B[b]) {
                        B[b] = lay;
                        next.push_back(btoa[b]);
                    }
                }
            if (islast) break;
            if (next.empty()) return res;
            for (int a : next) A[a] = lay;
            cur.swap(next);
        }
        /// Use DFS to scan for augmenting paths.
        rep(a,0,sz(g))
        res += dfs(a, 0, g, btoa, A, B);
    }
}

int main() {
    int xl, yl;
    cin >> xl >> yl;
    string input[xl * 2 - 1];
    for (int y = 0; y < yl * 2 - 1; ++y) {
        cin >> input[y];
    }
    bool req[xl][yl];
    for (int x = 0; x < xl; ++x) {
        for (int y = 0; y < yl; ++y) {
            if ((x == 0 || x == xl - 1) && (y == 0 || y == yl - 1)) {
                req[x][y] = input[x * 2][y * 2] == '2';
            } else if (!(x == 0 || x == xl - 1) && !(y == 0 || y == yl - 1)) {
                req[x][y] = input[x * 2][y * 2] == '7';
            } else {
                req[x][y] = input[x * 2][y * 2] == '4';
            }
        }
    }
    map<pair<int,int>, int> mpe;
    for (int x = 0; x < xl; ++x) {
        for (int y = 0; y < yl; ++y) {
            if ((x + y) % 2 == 0) {
                mpe[{x, y}] = mpe.size();
            }
        }
    }
    map<pair<int,int>, int> mpo;
    for (int x = 0; x < xl; ++x) {
        for (int y = 0; y < yl; ++y) {
            if ((x + y) % 2 == 1) {
                mpo[{x, y}] = mpo.size();
            }
        }
    }
    vector<vector<int>> ltr (mpe.size());
    for (int x = 0; x < xl; ++x) {
        for (int y = 0; y < yl; ++y) {
            if ((x + y) % 2 == 1 || !req[x][y]) continue;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= xl || ny < 0 || ny >= yl || !req[nx][ny]) continue;
                bool ise = x == 0 || x == xl - 1 || y == 0 || y == yl - 1;
                bool nse = nx == 0 || nx == xl - 1 || ny == 0 || ny == yl - 1;
                if ((ise && !nse) || (!ise && nse)) continue;
                ltr[mpe[{x, y}]].push_back(mpo[{nx, ny}]);
            }
        }
    }
    vector<int> matches (mpo.size(), -1);
    hopcroftKarp(ltr, matches);

    for (int x = 0; x < xl; ++x) {
        for (int y = 0; y < yl; ++y) {
            if ((x + y) % 2 == 0 || !req[x][y]) continue;
            if (matches[mpo[{x, y}]] == -1) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    for (int x = 0; x < xl; ++x) {
        for (int y = 0; y < yl; ++y) {
            if ((x + y) % 2 == 1 || !req[x][y]) continue;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= xl || ny < 0 || ny >= yl || !req[nx][ny]) continue;
                if (matches[mpo[{nx, ny}]] == mpe[{x, y}]) {
                    input[x * 2 + dx[i]][y * 2 + dy[i]] = '#';
                }
            }
        }
    }
    cout << "YES" << endl;
    for (int i = 0; i < yl * 2 - 1; ++i) {
        for (char& c : input[i]) {
            if (c == '#') {
                c = '.';
            } else if (c == '.') {
                c = '#';
            }
        }
        cout << input[i] << endl;
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

2 2
2.2
...
2.2

output:

YES
2.2
###
2.2

result:

ok Correct.

Test #4:

score: -100
Runtime Error

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: