QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#603090 | #8720. BFS 序 0 | Kanate# | WA | 0ms | 24084kb | C++14 | 3.2kb | 2024-10-01 14:39:38 | 2024-10-01 14:39:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rint int
#define endl '\n'
#define uint unsigned long long
void debug(int *a,int n){for(rint i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;}
void debug(int *a){for(rint i=1;a[i];i++) cout<<a[i]<<" ";cout<<endl;}
void debug(int x){cout<<"debug: "<<x<<endl;}
int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c))x=x*10+c-48,c=getchar();
return x*f;
}const int N=3e5+10,p=1e9,mod=998244353;
int n;
vector<int> e[N];
int d[N],FA[N],sz[N],son[N],top[N],dfn[N],idx;
void dfs(int x=1,int fa=1,int dep=1)
{
d[x]=dep,FA[x]=fa,sz[x]=1;
for(auto &it:e[x])
if(it!=fa)
{
dfs(it,x,dep+1);
sz[x]+=sz[it];
if(sz[it]>sz[son[x]]) son[x]=it;
}
}
void dfs2(int x=1,int tp=1)
{
top[x]=tp,dfn[x]=++idx;
if(!son[x]) return;
dfs2(son[x],tp);
for(auto &it:e[x])
if(it!=FA[x]&&it!=son[x]) dfs2(it,it);
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=FA[top[x]];
}
if(d[x]>d[y]) swap(x,y);
return x;
}
int dis(int x,int y)
{
return d[x]+d[y]-2*d[lca(x,y)];
}
struct tree{
int v[N<<2];
void build(int l=1,int r=n,int now=1)
{
v[now]=p;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,now<<1),build(mid+1,r,now<<1|1);
}
void modify(int k,int x,int l=1,int r=n,int now=1)
{
if(l==r) return v[now]=x,void();
int mid=(l+r)>>1;
if(l<=k) modify(k,x,l,mid,now<<1);
else modify(k,x,mid+1,r,now<<1|1);
v[now]=min(v[now<<1],v[now<<1|1]);
}
int ask(int ll,int rr,int l=1,int r=n,int now=1)
{
// cout<<ll<<" "<<rr<<" "<<l<<" "<<r<<" "<<now<<endl;
if(ll<=l&&r<=rr) return v[now];
int mid=(l+r)>>1,res=p;
if(ll<=mid) res=min(res,ask(ll,rr,l,mid,now<<1));
if(rr>mid) res=min(res,ask(ll,rr,mid+1,r,now<<1|1));
return res;
}
}t;
int m,b[N],c[N];
bool check()
{
b[m+1]=0;
for(rint i=1;i<m;i++) if(d[b[i]]>d[b[i+1]]) return 0;
for(rint i=1;i<=m+1;i++) c[i]=b[i];
for(rint l=1;l<=m;l++)
{
int r=l;
while(d[b[r+1]]==d[b[l]]) r++;
sort(c+l,c+r+1,[&](const int &A,const int &B){return dfn[A]<dfn[B];});
int nows=0;
for(rint i=l;i<r;i++) nows+=dis(b[i],b[i+1]);
int bess=0;
for(rint i=l;i<r;i++) bess+=dis(c[i],c[i+1]);
if(nows!=bess) return 0;
l=r;
}
// puts("get");
reverse(b+1,b+m+1);
for(rint l=1;l<=m;l++)
{
int r=l;
while(d[b[r+1]]==d[b[l]]) r++;
for(rint i=l;i<r;i++)
{
// puts("{");
int x=t.ask(dfn[b[i]],dfn[b[i]]+sz[b[i]]-1);
int y=t.ask(dfn[b[i+1]],dfn[b[i+1]]+sz[b[i+1]]-1);
// puts("}");
if(x&&y&&x>y)
{
for(rint j=1;j<l;j++) t.modify(dfn[b[j]],p);
return 0;
}
}
for(rint i=l;i<=r;i++) t.modify(dfn[b[i]],i);
l=r;
}
for(rint j=1;j<=m;j++) t.modify(dfn[b[j]],p);
return 1;
}
void Work()
{
n=read();
for(rint i=2;i<=n;i++)
e[read()].push_back(i);
dfs();
dfs2();
t.build();
int q=read();
while(q--)
{
m=read();
for(rint i=1;i<=m;i++) b[i]=read();
for(rint i=1;i<=m;i++) cout<<b[i]<<" ";cout<<endl;
puts(check()?"Yes":"No");
}
}
signed main()
{
// freopen("1.in","r",stdin);
Work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 24084kb
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:
3 6 2 5 No 4 Yes 2 4 5 Yes 2 5 4 6 3 No 1 4 2 No 5 6 3 No 4 5 2 6 1 No 4 3 2 5 No 4 6 2 3 No 3 2 6 Yes
result:
wrong output format YES or NO expected, but 3 found [1st token]