QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#409952 | #6746. Merge the Rectangles | Hirro | WA | 1145ms | 252664kb | C++14 | 2.4kb | 2024-05-12 23:08:44 | 2024-05-12 23:08:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1505;
int fa[N * N], siz[N * N];
int x1[N * N], x2[N * N], Y1[N * N], Y2[N * N];
int n, m;
int id(int x, int y) {
return (x * N + y);
}
int find(int x) {
if (fa[x] == x)return x;
else fa[x] = find(fa[x]);
return fa[x];
}
int tot;
void merge(int a, int b) {
find(a); find(b);
int x = fa[a], y = fa[b];
if (x == y)return;
if (siz[x] < siz[y])swap(x, y);
fa[y] = x;
siz[x] += siz[y];
x1[x] = min(x1[x], x1[y]);
x2[x] = max(x2[x], x2[y]);
Y1[x] = min(Y1[x], Y1[y]);
Y2[x] = max(Y2[x], Y2[y]);
tot--;
}
struct st{
int u, v, siz;
bool operator<(const st& a)const{
return siz < a.siz;
}
};
priority_queue<st>q;
void check(int u) {
int v;
if (Y2[u] + 1 <= n) {
v = id(x1[u], Y2[u] + 1);
find(v);
v = fa[v];
if (v != u && x1[v] == x1[u] && x2[v] == x2[u])q.push({ u,v,siz[u]+siz[v]});
}
if (Y1[u] - 1 >= 1) {
v = id(x1[u], Y1[u] - 1);
find(v);
v = fa[v];
if (v != u && x1[v] == x1[u] && x2[v] == x2[u])q.push({ u,v,siz[u] + siz[v] });
}
if (x1[u] - 1 >= 1) {
v = id(x1[u] - 1, Y1[u]);
find(v);
v = fa[v];
if (v != u && Y1[v] == Y1[u] && Y2[v] == Y2[u])q.push({ u,v,siz[u] + siz[v] });
}
if (x2[u] + 1 <= n) {
v = id(x2[u] + 1, Y1[u]);
find(v);
v = fa[v];
if (v != u && Y1[v] == Y1[u] && Y2[v] == Y2[u])q.push({ u,v,siz[u] + siz[v] });
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
tot = n*m;
for (int i = 0; i < N * N; i++)fa[i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int u = id(i, j);
x1[u] = x2[u] = i;
Y1[u] = Y2[u] = j;
}
}
for (int i = 1; i < n; i++) {
string s;
cin >> s;
s = " " + s;
for (int j = 1; j <= m; j++) {
if (s[j] == '1')continue;
merge(id(i, j), id(i + 1, j));
}
}
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
s = " " + s;
for (int j = 1; j < m; j++) {
if (s[j] == '1')continue;
merge(id(i, j), id(i, j + 1));
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int u = id(i, j);
if (fa[u] != u)continue;
check(u);
}
}
while (q.size()) {
int u = q.top().u;
int v = q.top().v;
q.pop();
if (Y1[v] == Y1[u] && Y2[v] == Y2[u])merge(u, v);
if (x1[v] == x1[u] && x2[v] == x2[u])merge(u, v);
int f = fa[u];
check(f);
}
if (tot == 1) {
cout << "YES\n";
}
else cout << "NO\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 21204kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 19796kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 27ms
memory: 48552kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 1070ms
memory: 244832kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 28ms
memory: 54832kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 27ms
memory: 50652kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #7:
score: 0
Accepted
time: 1079ms
memory: 247624kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #8:
score: 0
Accepted
time: 1087ms
memory: 252664kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #9:
score: 0
Accepted
time: 1081ms
memory: 252304kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #10:
score: 0
Accepted
time: 1145ms
memory: 251724kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #11:
score: -100
Wrong Answer
time: 1049ms
memory: 251048kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
wrong answer expected YES, found NO