QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#704206 | #7751. Palindrome Path | dread | WA | 3ms | 27388kb | C++14 | 2.1kb | 2024-11-02 19:30:42 | 2024-11-02 19:30:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int n, m, k;
struct Wall {
int x1, x2;
int id;
};
vector<Wall> wall[N];
vector<Wall> emp[N];
int cnt;
int par[N];
int findp(int x) {
if(x == par[x]) return x;
return par[x] = findp(par[x]);
}
void unite(int x, int y) {
x = findp(x);
y = findp(y);
if(x == y) return;
par[x] = y;
}
int get_len(const Wall &a, const Wall &b) {
int l1 = a.x1, r1 = a.x2;
int l2 = b.x1, r2 = b.x2;
if(l1 == r2) return 3;
else if(l2 == r1) return 1;
else if(l1 > r2) return -2;
else if(r1 < l2) return -1;
else return 2;
}
void solve() {
cin >> n >> m >> k;
if(n == 1) {
cout << "YES";
return;
}
if(m > 2 * k + 10) {
cout << "NO";
return;
}
// cout << "asdf\n";
for(int i = 1; i <= k; ++i) {
int x1, x2, y;
cin >> x1 >> x2 >> y;
wall[y].push_back({x1, x2, 0});
}
// cout << "asdf\n";
for(int i = 1; i <= m; ++i) {
sort(wall[i].begin(), wall[i].end(), [&](const auto &a, const auto &b) {
return a.x1 < b.x1;
});
int l = 1;
for(auto t:wall[i]) {
if(l != t.x1) {
emp[i].push_back({l, t.x1 - 1, ++cnt});
}
l = t.x2 + 1;
}
if(l != n + 1) {
emp[i].push_back({l, n, ++cnt});
}
}
for(int i = 1; i <= cnt; ++i) {
par[i] = i;
}
for(int i = 1; i < m; ++i) {
int p1, p2;
p1 = p2 = 0;
while(p1 < emp[i].size() && p2 < emp[i + 1].size()) {
// cout << p1 << " " << p2 << endl;
int t = get_len(emp[i][p1], emp[i + 1][p2]);
if(t == 1 || t == 3) {
int x = emp[i][p1].id;
int y = emp[i + 1][p2].id;
x = findp(x);
y = findp(y);
if(x == y) {
cout << "NO\n";
return;
}
unite(x, y);
if(t == 1) p1++;
else p2++;
} else if(t == 2) {
cout << "NO\n";
return;
} else if(t == -1) {
p1++;
} else {
p2++;
}
}
}
cout << "YES\n";
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 27388kb
input:
2 2 11 11 1 1 2 2
output:
YES
result:
wrong answer Line [name=User Output] equals to "YES", doesn't correspond to pattern "-1|[LRUD]{0,1000000}"