QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#622497 | #7752. The Only Way to the Destination | Saton | RE | 0ms | 3672kb | C++20 | 2.4kb | 2024-10-08 22:09:06 | 2024-10-08 22:09:06 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
struct wall
{
int x1, x2, y;
bool operator<(wall x)
{
if (y != x.y)
return y<x.y;
return x1 < x.x1;
}
}w[10000];
int n, m, k;
struct node
{
int l, r, color; // 记录连续空区间的左右端点,及其颜色
};
vector<node> lst, cur; // lst表示前一列的空区间, cur 表示当前枚举这一列的空区间
int c, f[10000];
// 使用并查集,保持统一性
int find(int x)
{
if(x!=f[x]) f[x] = find(f[x]);
return f[x];
}
void merge(int x, int y)
{
f[find(y)] = find(x);
}
int findl(int l)
{
for (int i=0; i<lst.size(); ++i)
if (lst[i].r >= l)
return i;
return -1;
}
int findr(int r)
{
for (int i=lst.size()-1; i>=0; --i)
{
if (lst[i].l <= r)
return i;
}
return -1;
}
bool solve()
{
if (n == 1)
return true;
for (int i=1; i<10000; ++i)
f[i] = i;
for (int col = 1, i = 0,lstr; col<=m; ++col)
{
lstr = 0; // 记录上一个墙的右端点, 因此可以计算出下一段空区间为[lstr+1, w[].x1-1]
cur.clear();
while(i+1<=k && w[i+1].y == col)
{
i++;
if (lstr+1 <= w[i].x1-1)
{
cur.push_back((node){lstr+1, w[i].x1-1, -1}); // 中间有空隙
}
lstr = w[i].x2;
}
if (lstr+1 <= n)
cur.push_back((node){lstr+1, n, -1});
int l, r, lidx, ridx, lstf; // 枚举空区间的左右端点,以及前一个左右区间
for (auto &tmp: cur)
{
l = tmp.l;
r = tmp.r;
lidx = findl(l);
ridx = findr(r);
lstf = -1; // 所属颜色
for (int i=lidx, tl, tr;i>=0 && i<=ridx; ++i)
{
// if(lst[i].r < l) continue;
tl = max(l, lst[i].l);
tr = min(r, lst[i].r);
if (tr - tl >= 1)
return false;
if (lstf != -1)
{
if (find(lst[i].color != lstf))
merge(lstf, lst[i].color);
else
return false; // 两个颜色已经连通
}
else
lstf = find(lst[i].color);
}
if (lstf != -1)
tmp.color = lstf;
else
{
tmp.color = c;
c++;
}
}
lst = cur; //对lst重新初始化 使其表示前一列
}
return true;
}
int main()
{
cin >> n >> m >> k;
for (int i=1; i<=k; ++i)
{
cin >> w[i].x1 >> w[i].x2 >> w[i].y;
}
sort(w+1, w+k+1);
if (solve())
cout << "yes";
else
cout << "no";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3672kb
input:
5 3 2 2 5 1 1 4 3
output:
yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
5 3 1 2 4 2
output:
no
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
2 4 2 2 2 1 1 1 4
output:
no
result:
ok answer is NO
Test #4:
score: -100
Runtime Error
input:
409455775 596220461 69036 72554058 85866426 497212608 54242898 110165840 236869995 68671059 127632371 324336242 39386477 208393446 248270338 151972182 327931056 231832 36658944 75335495 293646122 29512382 138875677 205628469 149151850 327396301 590717922 114980184 165064700 323939243 1771834 7016377...