QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#413561 | #6746. Merge the Rectangles | SSHL# | TL | 97ms | 18004kb | C++14 | 6.1kb | 2024-05-17 18:42:24 | 2024-05-17 18:42:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1510;
#define PII pair<int, int>
#define x first
#define y second
int a[N][N];
char sb[N][N], hb[N][N];
int st[N][N], idx;
int n, m;
int maxn = 0;
void bfs(int x, int y)
{
queue<PII> q;
st[x][y] = ++idx;
q.push({x, y});
while (q.size())
{
auto tmp = q.front();
q.pop();
// cout << x << ' ' << y << ' ' << tmp.x << ' ' << tmp.y << endl;
if ((tmp.x - 1) >= 1 && st[tmp.x - 1][tmp.y] == 0 && hb[tmp.x - 1][tmp.y] == '0')
{
// cout << x << ' ' << y << ' ' << tmp.x << ' ' << tmp.y << endl;
q.push({tmp.x - 1, tmp.y});
st[tmp.x - 1][tmp.y] = st[tmp.x][tmp.y];
}
if ((tmp.x + 1) <= n && st[tmp.x + 1][tmp.y] == 0 && hb[tmp.x][tmp.y] == '0')
{
// cout << x << ' ' << y << ' ' << tmp.x << ' ' << tmp.y << endl;
q.push({tmp.x + 1, tmp.y});
st[tmp.x + 1][tmp.y] = st[tmp.x][tmp.y];
}
if ((tmp.y + 1) <= m && st[tmp.x][tmp.y + 1] == 0 && sb[tmp.x][tmp.y] == '0')
{
// cout << x << ' ' << y << ' ' << tmp.x << ' ' << tmp.y << endl;
q.push({tmp.x, tmp.y + 1});
st[tmp.x][tmp.y + 1] = st[tmp.x][tmp.y];
}
if ((tmp.y - 1) >= 1 && st[tmp.x][tmp.y - 1] == 0 && sb[tmp.x][tmp.y - 1] == '0')
{
// cout << x << ' ' << y << ' ' << tmp.x << ' ' << tmp.y << endl;
q.push({tmp.x, tmp.y - 1});
st[tmp.x][tmp.y - 1] = st[tmp.x][tmp.y];
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++)
cin >> hb[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++)
cin >> sb[i][j];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (!st[i][j])
{
bfs(i, j);
}
}
}
set<int> sss;
map<int, pair<int, int>> zs, zx, ys, yx;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
// cout << st[i][j] << ' ';
maxn = max(st[i][j], maxn);
if (zs[st[i][j]].first > i && zs[st[i][j]].second > j || zs[st[i][j]].first > i && zs[st[i][j]].second == j || zs[st[i][j]].first == i && zs[st[i][j]].second > j || zs[st[i][j]].first == 0)
{
zs[st[i][j]] = {i, j};
}
if (zx[st[i][j]].first < i || zx[st[i][j]].first == i && zx[st[i][j]].second > j || zx[st[i][j]].first == 0)
{
zx[st[i][j]] = {i, j};
}
if (ys[st[i][j]].second < j || ys[st[i][j]].first == j && ys[st[i][j]].second > i || ys[st[i][j]].first == 0)
{
ys[st[i][j]] = {i, j};
}
if (yx[st[i][j]].first < i && yx[st[i][j]].second < j || yx[st[i][j]].first < i && yx[st[i][j]].second == j || yx[st[i][j]].first == i && yx[st[i][j]].second < j || yx[st[i][j]].first == 0)
{
yx[st[i][j]] = {i, j};
}
}
}
int cnt = 0;
// for(int i=1;i<=maxn;i++)
// {
// cout<<i<<endl;
// cout<<"zs"<<zs[i].first<<" "<<zs[i].second<<endl;
// cout<<"zx"<<zx[i].first<<" "<<zx[i].second<<endl;
// cout<<"ys"<<ys[i].first<<" "<<ys[i].second<<endl;
// cout<<"yx"<<yx[i].first<<" "<<yx[i].second<<endl;
// }
// set<pair<int, array<int, 4>>> s;
// for (int i = 1; i <= idx; i++)
// {
// ;
// }
// cout << cnt << endl;
bool f = 0;
while (1)
{
int tmp=cnt;
for (int i = 1; i <= maxn; i++)
{
for (int j = 1; j <= maxn; j++)
{
if(cnt==maxn-1)
{
f=1;
goto out;
}
if (i == j || sss.count(j))
{
continue;
}
if (zs[i].first == ys[j].first && zs[i].second - 1 == ys[j].second && zx[i].first == yx[j].first && zx[i].second - 1 == yx[j].second)
{
zs[i].first = zs[j].first;
zs[i].second = zs[j].second;
zx[i].first = zx[j].first;
zx[i].second = zx[j].second;
sss.insert(j);
cnt++;
}
if (zs[j].first == ys[i].first && zs[j].second - 1 == ys[i].second && zx[j].first == yx[i].first && zx[j].second - 1 == yx[i].second)
{
ys[i].first = ys[j].first;
ys[i].second = ys[j].second;
yx[i].first = yx[j].first;
yx[i].second = yx[j].second;
sss.insert(j);
cnt++;
}
if (zs[i].first - 1 == zx[j].first && zs[i].second == zx[j].second && ys[i].first - 1 == yx[j].first && ys[i].second == yx[j].second)
{
zs[i].first = zs[j].first;
zs[i].second = zs[j].second;
ys[i].first = ys[j].first;
ys[i].second = ys[j].second;
sss.insert(j);
cnt++;
}
if (zs[j].first == zx[i].first + 1 && zs[j].second == zx[i].second && ys[j].first == yx[i].first + 1 && ys[j].second == yx[i].second)
{
zx[i].first = zx[j].first;
zx[i].second = zx[j].second;
yx[i].first = yx[j].first;
yx[i].second = yx[j].second;
sss.insert(j);
cnt++;
}
}
}
if(tmp==cnt)
{
goto out;
}
}
out:
if (cnt == maxn - 1)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7664kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 7636kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 97ms
memory: 18004kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...