BFS?信友队上AC了,但CodeForces上wa掉

看一下错哪了
题目BFS?
id15654

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10;
int num[N];
int a[N];
int c[N];

int main(){
	int n;
	cin>>n;
	
	for(int i = 1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		num[x]++;
		a[y] = x;
	}
	
	for(int i = 1;i<=n;i++){
		cin>>c[i];
	}
	
	int k = 2;
	for(int i = 1;i<=n;i++){
		if(num[c[i]]){
			for(int j = k;j<=k+num[c[i]]-1;j++){
				if(a[c[j]]!=c[i]){
					cout<<"No"<<"\n";
					return 0;
				}
			}
		}k = k+num[c[i]];
	}
	cout<<"Yes"<<"\n";
	
	return 0;
}
5 个赞

信友队的题跟其他网站的题肯定有不一样,建议去把两题的题目及数据范围仔细比对一下。

6 个赞

不一定,也有可能是数据水

7 个赞

是不是题目不一样
毕竟不同的网站
也有可能是新友队本来就水

6 个赞

哪题呀

6 个赞

I. BFS?

Problem ID: 15654

Contest ID: 5942

必做题

题目描述

用BFS算法可以遍历得到一棵树,但是根据遍历结点顺序的不同,最终得到的序列也不同。

在这个问题中,给你一个序列和一棵根结点为1的树,你需要判断通过BFS遍历得到的序列是否和所给序列相同。

输入示例

第一行输入一个整数n(1≤n≤2∗105),表示树的点数。

接下来n−1行,每行输入两个整数x和y(1≤x,y≤n),表示一条边。数据保证所给的图是一棵树。

最后一行包含了n个整数a1,a2,…,an(1≤ai≤n),表示需要判断的序列。

输出示例

如果能通过BFS得到所给的序列,输出"Yes",否则输出"No"。

样例1

输入样例

4 1 2 1 3 2 4 1 3 2 4

输出样例

Yes

样例2

输入样例

4 1 2 1 3 2 4 1 2 4 3

输出样例

No

样例说明

两个样例所给的树是相同的,这颗树可以得到两种不同的BFS序列:

  • 1,2,3,4
  • 1,3,2,4

样例2的1,2,4,3并不能与上述BFS序列相匹配。

6 个赞

已知我不会所以我不会

6 个赞

题目一样的

6 个赞

确实是数据水,而且codeforces上样例下不下来

6 个赞

一样的

6 个赞

啊对

6 个赞

众所周知,信友队的AC代码放到洛谷上20%都会WA,其实是因为我太蒟蒻了

5 个赞

老师帮我找到问题了,

for(int i = 1;i<=n-1;i++){
	int x,y;
	cin>>x>>y;
	num[x]++;
	a[y] = x;
}

这一段建边错了,应该建的是双向边

6 个赞

你们算法的聊吧,我不懂

6 个赞

会不会有时候洛谷上AC的题目放到信友队上就会WA

6 个赞

没碰到过 :grinning:

4 个赞

ThomasZhao 遇到过
导弹拦截

4 个赞

不会吧,导弹拦截洛谷上要用nlogn的,信友队只要n^2

3 个赞

此贴了解一下

2 个赞

1 个赞