QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#593335 | #7752. The Only Way to the Destination | ucup-team1074 | WA | 0ms | 3816kb | C++23 | 3.3kb | 2024-09-27 13:21:44 | 2024-09-27 13:21:45 |
Judging History
answer
// Problem: G - The Only Way to the Destination
// Contest: Virtual Judge - 第九届中国大学生程序设计竞赛 哈尔滨站(CCPC 2023 Harbin Site)
// URL: https://vjudge.net/contest/658339#problem/G
// Memory Limit: 507 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
struct Point{
int x1 , x2 , y , id;
};
void solve()
{
int n , m , k;
cin >> n >> m >> k;
int idx = 0;
if(k * 3 < m){
cout << "NO\n";
}
else{
//判环
vector<Point>p;
vector<int> edge[m + k * 3 + 5];
array<int,3> wall[k];
for(int i = 0 ; i < k ; i ++){
cin >> wall[i][1] >> wall[i][2] >> wall[i][0];
}
sort(wall , wall + k);
int top = 0;
int l = 1;
int ll = 0;
p.pb({0 , 0 , 0 , 0});
for(int i = 1 ; i <= m ; i ++){
int top = 0;
while(ll < k && wall[ll][0] <= i){
if(wall[ll][1] == 1){
top = wall[ll][2];
ll++;
break;
}
p.pb({top + 1 , wall[ll][1] - 1 , i , ++idx});
int f = 0;
while(l < idx && p[idx].y - p[l].y > 1){
l++;
}
while(l < idx && p[idx].y - p[l].y == 1){
if(p[l].x2 < p[idx].x1){
l++;
continue;
}
int mi = max(p[l].x1 , p[idx].x1);
int mx = min(p[l].x2 , p[idx].x2);
if(mx > mi && p[l].x2 - p[l].x1 > 1 && p[idx].x2 - p[idx].x1 > 1){
cout << "NO\n";
return;
}
edge[l].pb(idx);
edge[idx].pb(l);
// cout << l << " " << idx << endl;
l++;
f = 1;
}
if(f){
l--;
}
top = wall[ll][2];
ll++;
}
if(top != n){
p.pb({top + 1 , n , i , ++idx});
int f = 0;
while(l < idx && p[idx].y - p[l].y > 1){
l++;
}
while(l < idx && p[idx].y - p[l].y == 1){
if(p[l].x2 < p[idx].x1){
l++;
continue;
}
int mi = max(p[l].x1 , p[idx].x1);
int mx = min(p[l].x2 , p[idx].x2);
if(mx > mi && p[l].x2 - p[l].x1 > 1 && p[idx].x2 - p[idx].x1 > 1){
cout << "NO\n";
return;
}
edge[l].pb(idx);
edge[idx].pb(l);
l++;
f = 1;
}
if(f){
l--;
}
}
}
/* for(int i = 1 ; i <= idx; i ++){
for(auto it : edge[i]){
cout << i << " " << it << endl;
}
}*/
vector<int>adj(idx + 5 , 0);
for(int i = 1 ; i <= idx ; i ++){
for(auto it : edge[i]){
adj[it]++;
// cout << i << " " << it << endl;
}
}
queue<int>q;
for(int i = 1 ; i <= idx ; i ++){
if(adj[i] == 1){
q.push(i);
}
}
while(!q.empty()){
int x = q.front();
q.pop();
for(auto it : edge[x]){
adj[it]--;
if(adj[it] == 1){
q.push(it);
}
}
}
for(int i = 1 ; i <= idx ; i ++){
if(adj[i] > 0){
cout << "NO\n";
return;
}
}
cout <<"YES\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
int t=1;
//cin>>t;
while(t--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
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: 3620kb
input:
5 3 1 2 4 2
output:
NO
result:
ok answer is NO
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3620kb
input:
2 4 2 2 2 1 1 1 4
output:
YES
result:
wrong answer expected NO, found YES