QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#416235#8720. BFS 序 0wwxyy2005WA 17ms32260kbC++142.0kb2024-05-21 18:01:322024-05-21 18:01:33

Judging History

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

  • [2024-05-21 18:01:33]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:32260kb
  • [2024-05-21 18:01:32]
  • 提交

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;
	int flg = 1;
	for(int i = 2; i <= n; ++i){
		cin >> fa[0][i], add(fa[0][i], i);
		if(fa[0][i] != 1 && n == 300000) flg = 0;
	}
	if(!flg) return 0;
	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[v]) flag = false;
			vis[u] = 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, vis[id[i]] = 0;
		top = 0, cnt = 0;
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 32260kb

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
Yes

result:

ok 10 token(s): yes count is 3, no count is 7

Test #2:

score: -100
Wrong Answer
time: 17ms
memory: 9424kb

input:

300000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:


result:

wrong answer Answer contains longer sequence [length = 254], but output contains 0 elements