QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#634253 | #7752. The Only Way to the Destination | asaltfish | WA | 1ms | 5692kb | C++23 | 5.0kb | 2024-10-12 16:57:29 | 2024-10-12 16:57:36 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<iomanip>
#include<stack>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define ll long long
#define endl "\n"
using namespace std;
int t, n, m, k, x1, x2, y, cnt, lg[200005], sum;
bool flag = 0;
struct wall
{
int x1, x2, y;
bool operator<(const wall& a) const
{
if (y == a.y)
{
return x1 < a.x1;
}
return y < a.y;
}
}ww[100005];
vector<wall>w[200005];
struct node
{
ll x1, x2, y, deg = 0;
};
vector<node>p[200005];
vector<int>e[200005];
int in[200005];
struct jh
{
ll x;
bool operator <(const jh& b)const
{
return in[x] > in[b.x];
}
};
void add(vector<node>& last, vector<node>& cur)
{
bool now;
int l = 0, r = 0;
while (r < cur.size() && l < last.size())
{
if (cur[r].x2 >= last[l].x2)now = 0;
if (!now)
{
while (l < last.size() && cur[r].x2 >= last[l].x2)
{
if (!cur[r].deg)cur[r].deg = ++cnt;
if (!last[l].deg)last[l].deg = ++cnt;
int l1 = last[l].x1, l2 = cur[r].x1, r1 = last[l].x2, r2 = cur[r].x2;
if (r1 < l2)
{
l++; continue;
}
if (min(r1, r2) - max(l1, l2) + 1 != 1)
{
flag = 1; return;
}
else {
//e[cur[r].deg].emplace_back(last[l].deg);
//e[last[l].deg].emplace_back(cur[r].deg);
sum++;
in[cur[r].deg]++;
in[last[l].deg]++;
l++;
}
}
}
else {
while (r < cur.size() && cur[r].x2 <= last[l].x2)
{
if (!cur[r].deg)cur[r].deg = ++cnt;
if (!last[l].deg)last[l].deg = ++cnt;
int l1 = last[l].x1, l2 = cur[r].x1, r1 = last[l].x2, r2 = cur[r].x2;
if (l2 < r1)
{
r++; continue;
}
if (min(r1, r2) - max(l1, l2) + 1 != 1)
{
flag = 1; return;
}
else {
//e[cur[r].deg].emplace_back(last[l].deg);
//e[last[l].deg].emplace_back(cur[r].deg);
in[cur[r].deg]++;
in[last[l].deg]++;
r++;
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
ll now = 0, last = 0;
for (int i = 1; i <= k; i++)
{
cin >> x1 >> x2 >> y;
cin>>ww[i].x1 >> ww[i].x2 >> ww[i].y;
}
sort(ww + 1, ww + k + 1);
for (int i = 1; i <= k; i++)
{
x1= ww[i].x1,x2= ww[i].x2 ,y= ww[i].y;
if (last != y) now++, last = y;
w[now].push_back(wall{ x1, x2, y });
}
for (int i = 1; i <= now; i++)
{
sort(w[i].begin(), w[i].end());
if (w[i][0].x1 > 1)
p[i].emplace_back(node{ 1,w[i][0].x1 - 1,w[i][0].y });
for (int j = 1; j < w[i].size(); j++)
{
if (w[i][j].x1 - w[i][j - 1].x2 > 0)
{
p[i].emplace_back(node{ w[i][j - 1].x2 + 1,w[i][j].x1 - 1,w[i][0].y });
}
}
if (w[i].back().x2 < n)
p[i].emplace_back(node{ w[i].back().x2 + 1,n,w[i][0].y });
}
while (now && p[now].back().y == m && p[now].empty())
{
lg[w[now].back().y] = 1;
m--;
now--;
}
int i = 1;
if (p[1].back().y == 1)
while (p[i].empty() && i <= now)
i++;
if (i > now || m - p[now].back().y > 1 || p[i][0].y > 2)
{
cout << "No"; return 0;
}
vector<node>la, nw;
if (p[i].back().y-i>1)
{
node kk = { 1,n,i + 1,0 };
la.push_back(kk);
}
else
{
nw = p[i];
i++;
}
for (; i <= now; i++)
{
la = nw;
nw = p[i];
if (nw.back().y - la.back().y > 2)
{
flag = 1; break;
}
else if (nw.back().y - la.back().y == 2)
{
nw.clear();
node kk = { 1,n,la.back().y + 1,0 };
nw.push_back(kk);
add(la, nw);
la = nw;
nw = p[i];
}
add(la, nw);
if (flag)
break;
}
if (nw.back().y != m)
{
la = nw;
nw.clear();
nw.push_back({ 1,n,m,0 });
}
if (flag)
{
cout << "No";
return 0;
}
//ll ans = 0;
//for (int i = 1; i <= n; i++)
//{
// ans += in[i];
//}
//ans /= 2;
if (sum + 1 == cnt)
cout << "Yes";
else
cout << "No";
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5692kb
input:
5 3 2 2 5 1 1 4 3
output:
No
result:
wrong answer expected YES, found NO