QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#741104 | #8720. BFS 序 0 | ucup-team4352# | WA | 2ms | 7672kb | C++23 | 2.9kb | 2024-11-13 13:21:45 | 2024-11-13 13:21:45 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define log(x) (31^__builtin_clz(x))
using namespace std;
const int maxn=3e5+5;
vector<int>e[maxn],s[maxn];
int f[maxn],dfn[maxn],dep[maxn];
int st[maxn][20],fa[maxn][20];
int tot;
inline int get(int x,int y){
return dep[x]<dep[y]?x:y;
}
int lca(int x,int y){
x=dfn[x];y=dfn[y];
if(x>y)swap(x,y);
x++;
int tmp=log(y-x+1);
return get(st[x][tmp],st[y-(1<<tmp)+1][tmp]);
}
void dfs(int x){
dfn[x]=++tot;
if(x==1)dep[x]=1;
fa[x][0]=st[dfn[x]][0];
for(int i=1;i<20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(auto u:e[x]){
dep[u]=dep[x]+1;
st[tot+1][0]=x;
dfs(u);
}
}
bool cmp(int a,int b){
return dfn[a]<dfn[b];
}
int flag=0;
int instack[maxn],vis[maxn];
int find(int x,int y){
for(int i=19;i>=0;i--){
if(y>>i&1)x=fa[x][i];
}
return x;
}
int build(vector<int>t){
sort(t.begin(),t.end(),cmp);
t.resize(unique(t.begin(),t.end())-t.begin());
for(int i=(int)t.size()-1;i;i--){
t.push_back(lca(t[i],t[i-1]));
}
sort(t.begin(),t.end(),cmp);
t.resize(unique(t.begin(),t.end())-t.begin());
for(auto u:t)s[u].clear(),vis[u]=instack[u]=0;
vector<int>st;
for(auto u:t){
if(st.empty())st.push_back(u);
else{
while(st.size()&&lca(st.back(),u)!=st.back())st.pop_back();
if(st.size()){
s[st.back()].push_back(u);
}
}
}
return t[0];
}
void dfs2(int x){
if(instack[x]){
flag=1;
return;
}
if(vis[x]||flag)return;
instack[x]=1;
vis[x]=1;
for(auto u:s[x]){
if(flag)break;
dfs2(u);
}
instack[x]=0;
}
void solve(){
int n;
cin>>n;
for(int i=2;i<=n;i++){
cin>>f[i];
e[f[i]].push_back(i);
}
dfs(1);
for(int i=n;i>=1;i--){
for(int j=1;j<20;j++){
st[i][j]=get(st[i][j-1],st[min(n,i+(1<<j-1))][j-1]);
}
}
int q;
cin>>q;
cout<<lca(4,7)<<"\n";
while(q--){
int m;
cin>>m;
vector<int>p;
flag=0;
for(int i=1;i<=m;i++){
int x;
cin>>x;
if(i>1){
if(dep[x]<dep[p.back()])flag=1;
}
p.push_back(x);
}
vector<int>p1=p;
for(int i=1;i<m;i++){
if(dep[p[i]]==dep[p[i-1]]){
int l=lca(p[i-1],p[i]);
int d=dep[p[i]]-dep[l]-1;
if(l)p1.push_back(find(p[i],d)),p1.push_back(find(p[i-1],d));
}
}
if(flag){
cout<<"No\n";
continue;
}
int rt=build(p1);
for(int i=0;i+1<p.size();i++){
if(dep[p[i]]==dep[p[i+1]]){
int l=lca(p[i+1],p[i]);
int d=dep[p[i]]-dep[l]-1;
// cout<<l<<" "<<d<<"!!!\n";
s[find(p[i],d)].push_back(find(p[i+1],d));
// cout<<find(p[i],d)<<" "<<find(p[i+1],d)<<"\n";
}
}
dfs2(rt);
if(flag){
cout<<"No\n";
continue;
}
cout<<"Yes\n";
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
/*
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7672kb
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:
0 No Yes Yes No No No No No No Yes
result:
wrong output format YES or NO expected, but 0 found [1st token]