QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#603090#8720. BFS 序 0Kanate#WA 0ms24084kbC++143.2kb2024-10-01 14:39:382024-10-01 14:39:41

Judging History

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

  • [2024-10-01 14:39:41]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:24084kb
  • [2024-10-01 14:39:38]
  • 提交

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;
}

詳細信息

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]