QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#390516#6746. Merge the Rectanglesucup-team1001WA 83ms128860kbC++234.8kb2024-04-15 16:24:252024-04-15 16:24:26

Judging History

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

  • [2024-04-15 16:24:26]
  • 评测
  • 测评结果:WA
  • 用时:83ms
  • 内存:128860kb
  • [2024-04-15 16:24:25]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

#ifndef ONLINE_JUDGE

#include "test.h"

#else
#define debug(...) 42
#define debug_assert(...) 42
#endif


#define IOS ios::sync_with_stdio(0),cin.tie(0)

using ll = long long;
using ull = unsigned long long;

#define endl '\n'
#define int ll

using VI = vector<int>;
using VII = vector<VI>;
using PII = pair<int, int>;
const int inf = 1e18;
const int mod = 1e9 + 7;
template<typename T, typename Compare =less<>>
using pqinit = priority_queue<T, vector<T>, Compare>;

void init() {
}

void solve() {
    int n, m;
    cin >> n >> m;
    int up = 1;
    int down = 2;
    int left = 4;
    int right = 8;
    int patten = (1 << 4 - 1);
    int upnode = patten ^ down;
    int downnode = patten ^ up;
    int leftnode = patten ^ right;
    int rightnode = patten ^ left;
    vector<vector<int>> arr(n + 3, vector<int>(m + 3));
    for (int i = 1; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == '1') {
                arr[i][j] |= left;
                arr[i][j + 1] |= right;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j < m; j++) {
            if (s[j - 1] == '1') {
                arr[i][j] |= down;
                arr[i + 1][j] |= up;
            }
        }
    }
    vector<vector<int>> mp1(n + 3, vector<int>(m + 3)), mp2(n + 3, vector<int>(m + 3)),
            du1(n + 3, vector<int>(m + 3)), du2(n + 3, vector<int>(m + 3));
    //  mp1  left -> down ->right -> up ->left
    //  mp2  up -> right -> down -> left -> up
    for (int i = 1; i < n; i++) {
        int lastRight = 0;
        for (int j = 1; j < m; j++) {
            if (arr[i][j] == rightnode) {
                lastRight = j;
            } else if (arr[i][j] == upnode && lastRight) {
                // 链接一个边
                mp2[i][j] = lastRight;
                du2[i][lastRight]++;
            } else if (arr[i][j] == downnode && lastRight) {
                mp1[i][j] = lastRight;
                du1[i][lastRight]++;
            }
        }
        int lastLeft = 0;
        for (int j = m; j >= 1; j--) {
            if (arr[i][j] == leftnode) {
                lastLeft = j;
            } else if (arr[i][j] == upnode && lastLeft) {
                mp1[i][j] = lastLeft;
                du1[i][lastLeft]++;
            } else if (arr[i][j] == downnode && lastLeft) {
                mp2[i][j] = lastLeft;
                du2[i][lastLeft]++;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        int lastDown = 0;
        for (int j = 1; j < n; j++) {
            if (arr[j][i] == downnode) {
                lastDown = j;
            } else if (arr[j][i] == leftnode && lastDown) {
                mp2[j][i] = lastDown;
                du2[lastDown][i]++;
            } else if (arr[j][i] == rightnode && lastDown) {
                mp1[j][i] = lastDown;
                du1[lastDown][i]++;
            }
        }
        int lastUp = 0;
        for (int j = n - 1; j >= 1; j--) {
            if (arr[j][i] == upnode) {
                lastUp = j;
            } else if (arr[j][i] == leftnode && lastUp) {
                mp1[j][i] = lastUp;
                du1[lastUp][i]++;
            } else if (arr[j][i] == rightnode && lastUp) {
                mp2[j][i] = lastUp;
                du2[lastUp][i]++;
            }
        }
    }

    int sizes = 0;
    queue<PII> q;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (du1[i][j] == 0) {
                q.push({i, j});
            }
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        sizes++;
        if (du1[x][y] == 0) {
            if (mp1[x][y]) {
                du1[mp1[x][y]][y]--;
                if (du1[mp1[x][y]][y] == 0) {
                    q.push({mp1[x][y], y});
                }
            }
        }
    }
    debug(sizes);
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (du2[i][j] == 0) {
                q.push({i, j});
            }
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        sizes++;
        if (du2[x][y] == 0) {
            if (mp2[x][y]) {
                du2[mp2[x][y]][y]--;
                if (du2[mp2[x][y]][y] == 0) {
                    q.push({mp2[x][y], y});
                }
            }
        }
    }
    debug(sizes);
    if (sizes == (n - 1) * (m - 1) * 2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

signed main() {
    IOS;
    init();
    // debug(1);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3872kb

input:

3 4
0000
0111
101
101
110

output:

Yes

result:

ok answer is YES

Test #2:

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

input:

3 3
110
011
01
11
10

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 71ms
memory: 128816kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 81ms
memory: 128860kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

Yes

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 83ms
memory: 128816kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

Yes

result:

ok answer is YES

Test #6:

score: 0
Accepted
time: 75ms
memory: 128832kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes

result:

ok answer is YES

Test #7:

score: -100
Wrong Answer
time: 76ms
memory: 128840kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

Yes

result:

wrong answer expected NO, found YES