QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412786 | #6746. Merge the Rectangles | p | WA | 92ms | 113460kb | C++17 | 2.8kb | 2024-05-16 19:30:02 | 2024-05-16 19:30:03 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int N = 1e3 + 5e2 + 10;
string ma[N];
struct node
{
int fg;
int pos;
int l, r;
bool operator<(const node &o) const
{
if (fg != o.fg)
return fg < o.fg;
if (pos != o.pos)
return pos < o.pos;
if (l != o.l)
return l < o.l;
return r < o.r;
}
};
map<node, int> num;
vector<node> arr[2][N][N];
signed main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i < n; i++)
{
cin>>ma[i];
ma[i]=" "+ma[i];
}
for (int i = 1; i < n; i++)
{
int l = -1;
for (int j = 1; j <= m + 1; j++)
{
if (j == m + 1 || ma[i][j] == '0')
{
if (l != -1)
{
node t = {1, i, l, j - 1};
num[t] = 2;
arr[1][i][j - 1].push_back(t);
arr[1][i][l].push_back(t);
}
l = -1;
}
else if (l == -1)
l = j - 1;
}
}
for (int i = 1; i <= n; i++)
{
cin >> ma[i];
ma[i] = " " + ma[i];
}
for (int j = 1; j < m; j++)
{
int l = -1;
for (int i = 1; i <= n + 1; i++)
{
if (i == n + 1 || ma[i][j] == '0')
{
if (l != -1)
{
node t = {0, j, l, i - 1};
num[t] = 2;
arr[0][l][j].push_back(t);
arr[0][i - 1][j].push_back(t);
}
l = -1;
}
else if (l == -1)
l = i - 1;
}
}
queue<node> que;
node t = {1, 0, 0, m};
que.push(t);
t = {1, n, 0, m};
que.push(t);
t = {0, 0, 0, n};
que.push(t);
t = {0, m, 0, n};
que.push(t);
while (que.size())
{
node t = que.front();
que.pop();
int pos = t.pos;
for (int i = t.l; i <= t.r; i++)
{
int x, y;
if (t.fg == 0)
x = i, y = pos;
else
x = pos, y = i;
for (auto c : arr[t.fg ^ 1][x][y])
{
num[c]--;
if (num[c] == 0)
que.push(c);
}
}
}
for (auto c : num)
{
// cout << c.first.fg << " " << c.first.pos << " " << c.first.l << "|" << c.first.r << " ";
if (c.second > 0)
{
cout << "NO\n";
return 0;
// cout << "!";
}
// cout << "\n";
}
cout << "YES\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 21ms
memory: 110480kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 8ms
memory: 110432kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 62ms
memory: 112900kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 87ms
memory: 113316kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 68ms
memory: 112828kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 74ms
memory: 113100kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #7:
score: 0
Accepted
time: 86ms
memory: 113320kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #8:
score: 0
Accepted
time: 60ms
memory: 113448kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #9:
score: 0
Accepted
time: 62ms
memory: 113148kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #10:
score: 0
Accepted
time: 92ms
memory: 113276kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #11:
score: 0
Accepted
time: 87ms
memory: 113152kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #12:
score: -100
Wrong Answer
time: 75ms
memory: 113460kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
wrong answer expected YES, found NO