QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390516 | #6746. Merge the Rectangles | ucup-team1001 | WA | 83ms | 128860kb | C++23 | 4.8kb | 2024-04-15 16:24:25 | 2024-04-15 16:24:26 |
Judging History
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