QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#416985#8720. BFS 序 0opbnbjsWA 3ms26500kbC++142.4kb2024-05-22 12:06:172024-05-22 12:06:18

Judging History

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

  • [2024-05-22 12:06:18]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:26500kb
  • [2024-05-22 12:06:17]
  • 提交

answer

#include<bits/stdc++.h>
#define V vector
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
const int maxn = 3e5+5;
int fno[maxn][35],dep[maxn];
V<int> g[maxn];
void dfs(int x,int fa){
	dep[x] = dep[fa]+1;
	fno[x][0] = fa;
	for(int i=1;i<=30;i++){
		fno[x][i] = fno[fno[x][i-1]][i-1];
	}
	for(auto i:g[x]){
		if(i==fa)	continue;
		dfs(i,x);
	}
}
set<int> f[maxn];
int lca(int x,int y){
	if(dep[x]>dep[y]) swap(x,y);
	int dif = dep[y]-dep[x];
	for(int i=0;dif;i++,dif>>=1){
		if(dif&1==1)	y = fno[y][i];
	}
	if(x==y) return x;
	for(int i=30;i>=0&&y!=x;i--){
		if(fno[x][i]!=fno[y][i]){
			x = fno[x][i];
			y = fno[y][i];
		}
	}
	return fno[x][0];
}
int getfa(int x,int y){
	if(dep[x]>dep[y]) swap(x,y);
	int dif = dep[y]-dep[x]-1;
	for(int i=0;dif;i++,dif>>=1){
		if(dif&1==1)	y = fno[y][i];
	}
	if(x==fno[y][0]) return y;
}
unordered_map<int,int> vis;
int ind[maxn];
void solve(){
	int n;
	cin>>n;
	for(int i=2;i<=n;i++){
		int fa;
		cin>>fa;
		g[fa].pb(i);
	}
	dfs(1,0);
	int q;
	cin>>q;
	while(q--){
		int m;
		cin>>m;
		V<int> seq;
		for(int i=1;i<=m;i++){
			int num;
			cin>>num;
			seq.pb(num);
		}
		bool flag=1;
      set<int> s;
      set<int>ones;
		for(int i=1;i<seq.size();i++){
			if(dep[seq[i]]<dep[seq[i-1]]){
				cout<<"No\n";
				flag=0;
				break;
			}
         if(dep[seq[i]]>dep[seq[i-1]]) continue;
			int l = lca(seq[i],seq[i-1]);
			int a,b;
         a = getfa(l,seq[i-1]);
         b = getfa(l,seq[i]);
			f[a].insert(b);
         ind[b]=1;
         ones.insert(b);
         s.insert(a);
		}
		if(flag==0){
         for(auto i:s)  f[i].clear();
         for(auto i:ones)  ind[i]=0;
         continue;
      }
      flag=0;
		for(auto i:s){
         if(ind[i]==1)  continue;
         flag=1;
         vis.clear();
			vis[i]=1;
			queue<int> q;
			q.push(i);
			while(!q.empty()){
				int x = q.front();
				q.pop();
				for(auto j:f[x]){
					if(vis[j]==1){
						flag=0;
						break;
					}
					vis[j]=1;
					q.push(j);
				}
				if(flag==0) break;
			}
			if(flag==0) break;
		}
		if(flag==0){
			cout<<"No\n";
         for(auto i:s)  f[i].clear();
         for(auto i:ones)  ind[i]=0;
         continue;
      }
      for(auto i:s)  f[i].clear();
      for(auto i:ones)  ind[i]=0;
		cout<<"Yes\n";
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 26500kb

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
No
Yes
No
No
No
No
No
No
Yes

result:

wrong answer expected YES, found NO [2nd token]