QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#603111#8720. BFS 序 0Kanate#WA 0ms30264kbC++143.6kb2024-10-01 14:44:562024-10-01 14:44:56

Judging History

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

  • [2024-10-01 14:44:56]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:30264kb
  • [2024-10-01 14:44:56]
  • 提交

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)
{
	if(lx>rx)return;
	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=-0x3f3f3f3f;
	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=0x3f3f3f3f;
	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];
int anc[500005][20];
void init()
{
	rep(i,1,n)anc[i][0]=fa[i];
	rep(j,1,19)
		rep(i,1,n)
			anc[i][j]=anc[anc[i][j-1]][j-1];
}
int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	per(i,19,0)
		if(dep[anc[u][i]]>=dep[v])
			u=anc[u][i];
	if(u==v)return v;
	per(i,19,0)
		if(anc[u][i]!=anc[v][i])
			u=anc[u][i],v=anc[v][i];
	return anc[u][0];
}
int dis(int u,int v)
{
	int l=lca(u,v);
	return dep[u]-dep[l]+dep[v]-dep[l];
}

void solve()
{
	read(m);
	rep(i,1,m)read(a[i]);
	a[m+1]=a[m+2]=0;

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

	assign(1,n,0x3f3f3f3f+1);
	per(i,m,1)
	{
		if(i!=1)if(dep[a[i]]==dep[a[i-1]])
		{
			int q1=query2(dfn[a[i]],dfn[a[i]]+siz[a[i]]-1);
			int q2=query2(dfn[a[i-1]],dfn[a[i-1]]+siz[a[i-1]]-1);
			// write(i,' '),write(q1,' '),write(q2,'\n');
			if(q1<0x3f3f3f3f&&q2<0x3f3f3f3f)
				if(q1<q2){puts("No");return;}
		}
		assign(dfn[a[i]],dfn[a[i]],i+1);
	}

	int lst=1;
	rep(i,1,m)if(m==i||dep[a[i]]!=dep[a[i+1]])
	{
		int dis1=0,dis2=0;
		rep(j,lst,i-1)
			dis1+=dis(a[j],a[j+1]);
		sort(a+lst,a+1+i,[](int a,int b){return dfn[a]<dfn[b];});
		rep(j,lst,i-1)
			dis2+=dis(a[j],a[j+1]);
		write(dis1,' ');write(dis2,'\n');
		if(dis1!=dis2){puts("No");return;}
		lst=i+1;
	}

	puts("Yes");
}
signed main()
{
	read(n);
	rep(i,2,n)
	{
		read(fa[i]);
		g[fa[i]].push_back(i);
	}
	dfs(1);
	init();
	read(q);
	rep(i,1,q)solve();
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 30264kb

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
0 0
Yes
0 0
4 4
Yes
No
No
No
No
No
No
2 2
0 0
Yes

result:

wrong output format YES or NO expected, but 0 found [2nd token]