QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#603295 | #8720. BFS 序 0 | UESTC_DebugSimulator | WA | 0ms | 18260kb | C++17 | 3.0kb | 2024-10-01 15:45:03 | 2024-10-01 15:45:04 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lowbit(i) (i&-i)
#define rand() (myrand())
using namespace std;
mt19937 myrand(time(0));
const int maxn = 5e5 + 5;
int n, _, q, m, dfn[maxn], cnt, now[maxn], head[maxn], tot, dep[maxn], fa[maxn];
struct EDGE{
int next, to;
}edge[maxn<<1];
void addedge(int from, int to) {
edge[++cnt].next = head[from];
edge[cnt].to = to;
head[from] = cnt;
}
namespace Segtr{
int vmax[maxn<<2], vmin[maxn<<2];
int searchmin(int x, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return vmin[x];
int mid = (l + r)>>1;
if (ql <= mid && qr > mid) return min(searchmin(x<<1, l, mid, ql, qr), searchmin(x<<1|1, mid + 1, r, ql, qr));
if (ql > mid) return searchmin(x<<1|1, mid + 1, r, ql, qr);
return searchmin(x<<1, l, mid, ql, qr);
}
int searchmax(int x, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return vmax[x];
int mid = (l + r)>>1;
if (ql <= mid && qr > mid) return max(searchmax(x<<1, l, mid, ql, qr), searchmax(x<<1|1, mid + 1, r, ql, qr));
if (ql > mid) return searchmax(x<<1|1, mid + 1, r, ql, qr);
return searchmax(x<<1, l, mid, ql, qr);
}
void modify(int x, int l, int r, int ql, int t) {
if (l == r) {
if (t == 0) {
vmin[x] = 1e9;
vmax[x] = 0;
return;
}
vmin[x] = vmax[x] = t;
return;
}
int mid = (l + r)>>1;
if (ql <= mid) modify(x<<1, l, mid, ql, t);
else modify(x<<1|1, mid + 1, r, ql, t);
vmin[x] = min(vmin[x<<1], vmin[x<<1|1]);
vmax[x] = max(vmax[x<<1], vmax[x<<1|1]);
}
}
void dfs(int u, int p) {
dfn[u] = ++tot;
dep[u] = dep[p] + 1;
fa[u] = p;
for (int i = head[u] ; i ; i = edge[i].next) {
int v = edge[i].to;
if (v == p) continue;
dfs(v, u);
}
now[u] = tot;
}
void solve() {
cin >> n;
for (int i = 1 ; i <= (maxn<<2) - 5 ; ++i) Segtr::vmin[i] = 1e9;
for (int i = 2 ; i <= n ; ++i) {
int p;
cin >> p;
addedge(i, p);
addedge(p, i);
}
dfs(1, 0);
cin >> q;
for (int i = 1 ; i <= q ; ++i) {
cin >> m;
vector<int>pt(m + 1);
int jud = 0;
for (int j = 1 ; j <= m ; ++j) {
cin >> pt[j];
if (j > 1 && dep[pt[j]] < dep[pt[j - 1]]) jud = 1;
}
if (jud == 1) {
cout << "No" << '\n';
continue;
}
int p = m;
while(p >= 1) {
int l = p, r = p, pre = 0;
while(l - 1 >= 1 && dep[pt[l]] == dep[pt[l - 1]]) l--;
for (int j = l ; j <= r ; ++j) Segtr::modify(1, 1, n, dfn[pt[j]], j);
for (int j = l ; j <= r ; ++j) {
int vmax = Segtr::searchmax(1, 1, n, dfn[pt[j]], now[pt[j]]);
int vmin = Segtr::searchmin(1, 1, n, dfn[pt[j]], now[pt[j]]);
if (vmin < pre) jud = 1;
pre = max(pre, vmax);
}
for (int j = l ; j <= r ; ++j)Segtr::modify(1, 1, n, dfn[pt[j]], j);
p = l - 1;
}
for (int j = 1 ; j <= m ; ++j) Segtr::modify(1, 1, n, dfn[pt[j]], 0);
cout << (jud == 1 ? "No" : "Yes") << '\n';
}
}
signed main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 18260kb
input:
6 1 1 3 2 4 10 4 3 6 2 5 1 4 3 2 4 5 5 2 5 4 6 3 3 1 4 2 3 5 6 3 5 4 5 2 6 1 4 4 3 2 5 4 4 6 2 3 3 3 2 6
output:
No Yes Yes No No No No No No No
result:
wrong answer expected YES, found NO [10th token]