QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#412784 | #6746. Merge the Rectangles | p | WA | 173ms | 113392kb | C++17 | 2.9kb | 2024-05-16 19:28:51 | 2024-05-16 19:28:52 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int N = 1e3 + 5e2 + 10;
char ma[N][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++)
for (int j = 1; j <= m; j++)
cin >> ma[i][j];
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;
}
}
memset(0, sizeof ma, 0);
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++)
cin >> ma[i][j];
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";
}
詳細信息
Test #1:
score: 100
Accepted
time: 11ms
memory: 111936kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 7ms
memory: 110732kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 153ms
memory: 112556kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 170ms
memory: 112980kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 156ms
memory: 113040kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 157ms
memory: 112948kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #7:
score: 0
Accepted
time: 166ms
memory: 112900kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #8:
score: 0
Accepted
time: 151ms
memory: 113108kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #9:
score: 0
Accepted
time: 143ms
memory: 113380kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #10:
score: 0
Accepted
time: 173ms
memory: 113132kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #11:
score: 0
Accepted
time: 163ms
memory: 113196kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #12:
score: -100
Wrong Answer
time: 149ms
memory: 113392kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
wrong answer expected YES, found NO