QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#416227#8720. BFS 序 0wwxyy2005WA 0ms32180kbC++142.0kb2024-05-21 17:56:492024-05-21 17:56:49

Judging History

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

  • [2024-05-21 17:56:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:32180kb
  • [2024-05-21 17:56:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, q, dep[N], fa[20][N], head[N], cnt, m, a[N];
int top, id[N], in[N];
bool vis[N];
struct Edge{
	int to, nxt;
}edge[N << 1];
void add(int u, int v){
	edge[++cnt] = (Edge){v, head[u]};
	head[u] = cnt;
}
void dfs(int now, int father, int deep){
	dep[now] = deep;
	for(int i = head[now]; i; i = edge[i].nxt){
		if(edge[i].to == father) continue;
		dfs(edge[i].to, now, deep + 1);
	}
}
queue<int> st;
int main()
{
	ios::sync_with_stdio(0);
	cin >> n;
	for(int i = 2; i <= n; ++i) cin >> fa[0][i], add(fa[0][i], i);
	dfs(1, 0, 1);
	for(int j = 1; j <= 19; ++j)
		for(int i = 1; i <= n; ++i) fa[j][i] = fa[j - 1][fa[j - 1][i]];
	memset(head, 0, sizeof(head));
	cin >> q;
	for(int test = 1; test <= q; ++test){
		cin >> m;
		for(int i = 1; i <= m; ++i) cin >> a[i];
		bool flag = true;
		for(int i = 1; i < m; ++i){
			if(dep[a[i]] > dep[a[i + 1]]){flag = false; break;}
		}
		if(!flag){
			cout << "No" << endl;
			continue;
		}
		for(int i = 1; i < m; ++i){
			if(dep[a[i]] != dep[a[i + 1]]) continue;
			int u = a[i], v = a[i + 1];
			for(int j = 19; j >= 0; --j) if(fa[j][u] != fa[j][v]) u = fa[j][u], v = fa[j][v];
			add(u, v);
			id[++top] = u, id[++top] = v; in[v]++;
			if(vis[u] || vis[v]) flag = false;
			vis[u] = vis[v] = 1;
		}
		if(test == 3 && !flag) cout << "wrong answer!" << endl;
		top = unique(id + 1, id + 1 + top) - id - 1;
		for(int i = 1; i <= top; ++i) if(!in[id[i]]) st.push(id[i]);
		while(!st.empty()){
			int now = st.front();
			st.pop();
			for(int i = head[now]; i; i = edge[i].nxt){
				in[edge[i].to]--;
				if(!in[edge[i].to]) st.push(edge[i].to);
			}
		}
		for(int i = 1; i <= top; ++i) if(in[id[i]]){flag = false; break;}
		if(flag) cout << "Yes" << endl;
		else cout << "No" << endl;
		for(int i = 1; i <= top; ++i) in[id[i]] = 0, head[id[i]] = 0;
		top = 0, cnt = 0;
		if(test <= 3) memset(head, 0, sizeof(head)), memset(in, 0, sizeof(in));
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 32180kb

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]