QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #622538 | #7752. The Only Way to the Destination | Saton | Compile Error | / | / | C++20 | 4.8kb | 2024-10-08 22:27:05 | 2024-10-08 22:27:06 |
Judging History
answer
# include <bits/stdc++.h>
#define int long long
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[100010];
int n, m, k;
struct node
{
int l, r, color; // 记录连续空区间的左右端点，及其颜色
};
vector<node> lst, cur; // lst表示前一列的空区间, cur 表示当前枚举这一列的空区间
int c, f[100010];
// 使用并查集，保持统一性
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<100010; ++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;
}
signed 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;
}# include <bits/stdc++.h>
#define int long long
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[100010];
int n, m, k;
struct node
{
int l, r, color; // 记录连续空区间的左右端点，及其颜色
};
vector<node> lst, cur; // lst表示前一列的空区间, cur 表示当前枚举这一列的空区间
int c, f[100010];
// 使用并查集，保持统一性
int find(int x)
{
if(x!=f[x]) f[x] = find(f[x]);
return f[x];
}
void merge(int x, int y)
{
f[find(x)] = find(y);
}
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<100010; ++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;
}
signed 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
answer.code:143:2: error: stray ‘#’ in program
143 | }# include <bits/stdc++.h>
| ^
answer.code:143:13: error: ‘bits’ was not declared in this scope
143 | }# include <bits/stdc++.h>
| ^~~~
answer.code:143:18: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
143 | }# include <bits/stdc++.h>
| ^~~~
| std
answer.code:143:13: error: ‘bits’ was not declared in this scope
143 | }# include <bits/stdc++.h>
| ^~~~
answer.code:143:18: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
143 | }# include <bits/stdc++.h>
| ^~~~
| std
answer.code:143:13: error: ‘bits’ was not declared in this scope
143 | }# include <bits/stdc++.h>
| ^~~~
answer.code:143:18: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
143 | }# include <bits/stdc++.h>
| ^~~~
| std
answer.code:143:13: error: ‘bits’ was not declared in this scope
143 | }# include <bits/stdc++.h>
| ^~~~
answer.code:143:18: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
143 | }# include <bits/stdc++.h>
| ^~~~
| std
answer.code:143:13: error: ‘bits’ was not declared in this scope
143 | }# include <bits/stdc++.h>
| ^~~~
answer.code:143:18: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
143 | }# include <bits/stdc++.h>
| ^~~~
| std
answer.code:143:13: error: ‘bits’ was not declared in this scope
143 | }# include <bits/stdc++.h>
| ^~~~
answer.code:143:18: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
143 | }# include <bits/stdc++.h>
| ^~~~
| std
answer.code:143:13: error: ‘bits’ was not declared in this scope
143 | }# include <bits/stdc++.h>
| ^~~~
answer.code:143:18: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
143 | }# include <bits/stdc++.h>
| ^~~~
| std
answer.code:143:13: error: ‘bits’ was not declared in this scope
143 | }# include <bits/stdc++.h>
| ^~~~
answer.code:143:18: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
143 | }# include <bits/stdc++.h>
| ^~~~
| std
answer.code:143:13: error: ‘bits’ was not declared in this scope
143 | }# include <bits/stdc++.h>
| ^~~~
answer.code:143:18: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
143 | }# include <bits/stdc++.h>
| ^~~~
| std
answer.code:143:4: error: ‘include’ does not name a type
143 | }# include <bits/stdc++.h>
| ^~~~~~~
answer.code:147:8: error: redefinition of ‘struct wall’
147 | struct wall
| ^~~~
answer.code:5:8: note: previous definition of ‘struct wall’
5 | struct wall
| ^~~~
answer.code:159:2: error: conflicting declaration ‘int w [100010]’
159 | }w[100010];
| ^
answer.code:17:2: note: previous declaration as ‘wall w [100010]’
17 | }w[100010];
| ^
answer.code:161:5: error: redefinition of ‘long long int n’
161 | int n, m, k;
| ^
answer.code:19:5: note: ‘long long int n’ previously declared here
19 | int n, m, k;
| ^
answer.code:161:8: error: redefinition of ‘long long int m’
161 | int n, m, k;
| ^
answer.code:19:8: note: ‘long long int m’ previously declared here
19 | int n, m, k;
| ^
answer.code:161:11: error: redefinition of ‘long long int k’
161 | int n, m, k;
| ^
answer.code:19:11: note: ‘long long int k’ previously declared here
19 | int n, m, k;
| ^
answer.code:163:8: error: redefinition of ‘struct node’
163 | struct node
| ^~~~
answer.code:21:8: note: previous definition of ‘struct node’
21 | struct node
| ^~~~
answer.code:168:14: error: redefinition of ‘std::vector<node> lst’
168 | vector<node> lst, cur; // lst表示前一列的空区间, cur 表示当前枚举这一列的空区间
| ^~~
answer.code:26:14: note: ‘std::vector<node> lst’ previously defined here
26 | vector<node> lst, cur; // lst表示前一列的空区间, cur 表示当前枚举这一列的空区间
| ^~~
answer.code:168:19: error: redefinition of ‘std::vector<node> cur’
168 | vector<node> lst, cur; // lst表示前一列的空区间, cur 表示当前枚举这一列的空区间
| ^~~
answer.code:26:19: note: ‘std::vector<node> cur’ previously defined here
26 | vector<node> lst, cur; // lst表示前一列的空区间, cur 表示当前枚举这一列的空区间
| ^~~
answer.code:170:5: error: redefinition of ‘long long int c’
170 | int c, f[100010];
| ^
answer.code:28:5: note: ‘long long int c’ previously declared here
28 | int c, f[100010];
...