QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#602645#8720. BFS 序 0Kanate#WA 327ms92408kbC++142.8kb2024-10-01 11:30:522024-10-01 11:30:53

Judging History

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

  • [2024-10-01 11:30:53]
  • 评测
  • 测评结果:WA
  • 用时:327ms
  • 内存:92408kb
  • [2024-10-01 11:30:52]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
//#define mod 1000000007
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
template<class T>void chkmax(T &a,T b){a=max(a,b);}
template<class T>void chkmin(T &a,T b){a=min(a,b);}
template<class T>T read(T &x)
{
	x=0;T f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^'0');c=getchar();}
	return x*=f;
}
template<class T,class ...L>void read(T &x,L &...l){read(x),read(l...);}
template<class T>void write(T x)
{
	if(x<0){putchar('-');x=-x;}
	if(x>9){write(x/10);}putchar(x%10+'0');
}
template<class T>void write(T x,char c){write(x),putchar(c);}

int dfnn;
int n,dfn[500005],dep[500005],siz[500005];
vector <int> g[500005];
void dfs(int u)
{
	dfn[u]=++dfnn;
	siz[u]=1;
	for(int v:g[u])
	{
		dep[v]=dep[u]+1;
		dfs(v);
		siz[u]+=siz[v];
	}
}

#define mid (l+r)/2
#define ls (o*2)
#define rs (o*2+1)
int seg1[500005<<3],seg2[500005<<3],tag[500005<<3];
void pushup(int o)
{
	seg1[o]=max(seg1[ls],seg1[rs]);
	seg2[o]=min(seg2[ls],seg2[rs]);
}
void pushdown(int o)
{
	if(!tag[o])return;
	tag[ls]=tag[rs]=tag[o];
	seg1[ls]=seg2[ls]=seg1[rs]=seg2[rs]=tag[o]-1;
	tag[o]=0;
	pushup(o);
}
void assign(int lx,int rx,int k,int o=1,int l=1,int r=n)
{
	pushdown(o);
	if(lx<=l&&r<=rx)
	{
		tag[o]=k;
		seg1[o]=k-1;
		seg2[o]=k-1;
		return;
	}
	if(lx<=mid)assign(lx,rx,k,ls,l,mid);
	if(rx>mid)assign(lx,rx,k,rs,mid+1,r);
	pushup(o);
}
int query1(int lx,int rx,int o=1,int l=1,int r=n)
{
	pushdown(o);
	if(lx<=l&&r<=rx)return seg1[o];
	int ans=0;
	if(lx<=mid)chkmax(ans,query1(lx,rx,ls,l,mid));
	if(rx>mid)chkmax(ans,query1(lx,rx,rs,mid+1,r));
	return ans;
}
int query2(int lx,int rx,int o=1,int l=1,int r=n)
{
	pushdown(o);
	if(lx<=l&&r<=rx)return seg2[o];
	int ans=1;
	if(lx<=mid)chkmin(ans,query2(lx,rx,ls,l,mid));
	if(rx>mid)chkmin(ans,query2(lx,rx,rs,mid+1,r));
	return ans;
}

int q,m,a[500005],fa[500005];
int vis[500005];
void solve()
{
	assign(1,n,1);
	read(m);
	rep(i,1,m)read(a[i]);

	rep(i,1,m)vis[a[i]]=0;
	rep(i,1,m)
	{
		if(vis[a[i]])
			{puts("No");return;}
		vis[a[i]]=1;
	}

	rep(i,1,m-1)
		if(dep[a[i]]>dep[a[i+1]])
			{puts("No");return;}

	rep(i,1,m)vis[a[i]]=0;
	rep(i,1,m)vis[fa[a[i]]]=0;
	rep(i,1,m)
	{
		if(i>=2)if(vis[fa[a[i]]])
			if(dep[a[i]]==dep[a[i-1]])
				if(fa[a[i]]!=fa[a[i-1]])
					{puts("No");return;}
		vis[fa[a[i]]]=1;
	}

	rep(i,1,m)
	{
		int l=dfn[a[i]];
		int r=dfn[a[i]]+siz[a[i]]-1;
		int q1=query1(l,r);
		int q2=query2(l,r);
		if(q1!=q2){puts("No");return;}
		assign(l,r,2);
	}
	puts("Yes");
}
signed main()
{
	read(n);
	rep(i,2,n)
	{
		read(fa[i]);
		g[fa[i]].push_back(i);
	}
	dfs(1);
	read(q);
	rep(i,1,q)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 28252kb

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

result:

ok 10 token(s): yes count is 3, no count is 7

Test #2:

score: -100
Wrong Answer
time: 327ms
memory: 92408kb

input:

300000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

No
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
No
No
No
Yes
No
No
Yes
No
No
No
No
Yes
Yes
Yes
No
No
Yes
No
No
No
No
No
No
No
Yes
No
Yes
No
Yes
No
No
No
No
Yes
Yes
Yes
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
No
No
No
Y...

result:

wrong answer expected NO, found YES [176th token]