QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#416985 | #8720. BFS 序 0 | opbnbjs | WA | 3ms | 26500kb | C++14 | 2.4kb | 2024-05-22 12:06:17 | 2024-05-22 12:06:18 |
Judging History
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]