QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661632 | #6746. Merge the Rectangles | ucup-team1769# | TL | 1ms | 3684kb | C++20 | 5.7kb | 2024-10-20 17:12:00 | 2024-10-20 17:12:02 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <map>
#include <cstring>
using namespace std;
using i64 = long long;
const int INF = 1e9 + 7;
const i64 mod = 998244353;
int n, m;
int vec[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void solve()
{
cin >> n >> m;
vector<string> a(n);
vector<string> b(n);
for (int i = 0; i < n - 1; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
vector<vector<int>> box(n + 3, vector<int>(m + 3, 0));
// vector<vector<bool>> vis(n + 3, vector<bool>(n + 3));
auto bfs = [&](int x, int y, int f) -> void
{
queue<pair<int, int>> q;
q.push({x, y});
while (!q.empty())
{
auto [ux, uy] = q.front();
box[ux][uy] = f;
q.pop();
for (auto [dx, dy] : vec)
{
int nx = ux + dx, ny = uy + dy;
if (nx < 1 || nx > n || ny < 1 || ny > m)
continue;
if (box[nx][ny])
continue;
// down
if (nx > ux && a[ux - 1][ny - 1] == '1')
continue;
// up
if (nx < ux && ux - 2 >= 0 && a[ux - 2][uy - 1] == '1')
continue;
// right
if (ny > uy && b[ux - 1][uy - 1] == '1')
continue;
// left
if (ny < uy && b[ux - 1][uy - 2] == '1')
continue;
q.push({nx, ny});
}
}
};
int cnt = 0;
vector<pair<int, int>> all;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (box[i][j])
continue;
bfs(i, j, ++cnt);
all.emplace_back(i, j);
}
}
//
map<pair<int, int>, pair<int, int>> mp1; // 左上角
map<pair<int, int>, pair<int, int>> mp2; // 右下角
queue<array<int, 4>> q;
for (int i = 1; i <= cnt; i++)
{
auto [x, y] = all[i - 1];
int x1 = x, y1 = y;
for (; box[x1 - 1][y1] == i; x1--)
;
for (; box[x1][y1 - 1] == i; y1--)
;
int x2 = x, y2 = y;
for (; box[x2 + 1][y2] == i; x2++)
;
for (; box[x2][y2 + 1] == i; y2++)
;
mp1.insert({{x1, y1}, {y2 - y1 + 1, x2 - x1 + 1}});
mp2.insert({{x2, y2}, {y2 - y1 + 1, x2 - x1 + 1}});
q.push({x1, y1, y2 - y1 + 1, x2 - x1 + 1});
}
while (q.size())
{
auto [ux, uy, w, h] = q.front();
q.pop();
// right
if (mp1.contains({ux, uy + w}))
{
auto [w1, h1] = mp1[{ux, uy + w}];
if (h1 == h)
{
q.push({ux, uy, w + w1, h});
mp1.erase({ux, uy});
mp1.erase({ux, uy + w});
mp2.erase({ux + h - 1, uy + w - 1});
mp2.erase({ux + h1 - 1, uy + w + w1 - 1});
mp1.insert({{ux, uy}, {w + w1, h}});
mp2.insert({{ux + h - 1, uy + w + w1 - 1}, {w + w1, h}});
continue;
}
}
// down
if (mp1.contains({ux + h, uy}))
{
auto [w1, h1] = mp1[{ux + h, uy}];
if (w1 == w)
{
q.push({ux, uy, w, h + h1});
mp1.erase({ux, uy});
mp1.erase({ux + h, uy});
mp2.erase({ux + h - 1, uy + w - 1});
mp2.erase({ux + h + h1 - 1, uy + w - 1});
mp1.insert({{ux, uy}, {w, h + h1}});
mp2.insert({{ux + h + h1 - 1, uy + w - 1}, {w, h + h1}});
continue;
}
}
// left
if (mp2.contains({ux + h - 1, uy - 1}))
{
auto [w1, h1] = mp2[{ux + h - 1, uy - 1}];
if (h1 == h)
{
q.push({ux, uy - w1, w1 + w, h});
mp1.erase({ux, uy});
mp1.erase({ux, uy - w1});
mp2.erase({ux + h - 1, uy + w - 1});
mp2.erase({ux + h - 1, uy - 1});
mp1.insert({{ux, uy - w1}, {w + w1, h}});
mp2.insert({{ux + h - 1, uy + w - 1}, {w + w1, h}});
continue;
}
}
// up
if (mp2.contains({ux - 1, uy + w - 1}))
{
auto [w1, h1] = mp2[{ux - 1, uy + w - 1}];
if (w1 == w)
{
q.push({ux - h1, uy, w, h1 + h});
mp1.erase({ux, uy});
mp1.erase({ux - h1, uy});
mp2.erase({ux + h - 1, uy + w - 1});
mp2.erase({ux - 1, uy + w - 1});
mp1.insert({{ux - h1, uy}, {w, h + h1}});
mp2.insert({{ux + h - 1, uy + w - 1}, {w, h + h1}});
continue;
}
}
}
if (mp1.contains({1, 1}))
{
auto [w, h] = mp1[{1, 1}];
if (w == m && h == n)
{
cout << "YES" << '\n';
}
else
{
cout << "NO" << '\n';
}
}
// for (auto [x, y] : mp1)
// {
// auto [_x, _y] = x;
// auto [__x, __y] = y;
// cerr << _x << ' ' << _y << " " << __x << " " << __y << '\n';
// }
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3684kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: -100
Time Limit Exceeded
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...