QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#603295#8720. BFS 序 0UESTC_DebugSimulatorWA 0ms18260kbC++173.0kb2024-10-01 15:45:032024-10-01 15:45:04

Judging History

你现在查看的是最新测评结果

  • [2024-10-01 15:45:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:18260kb
  • [2024-10-01 15:45:03]
  • 提交

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]