QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#419576#8720. BFS 序 0wcdrAC ✓46ms32352kbC++174.1kb2024-05-24 02:45:402024-05-24 02:45:41

Judging History

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

  • [2024-05-24 02:45:41]
  • 评测
  • 测评结果:AC
  • 用时:46ms
  • 内存:32352kb
  • [2024-05-24 02:45:40]
  • 提交

answer

#include<random>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<climits>
//#define NDEBUG
#include<cassert>
#include<cstring>
#include<complex>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<bitset>
//#define LL __int128
#define LL long long
#define ULL unsigned LL
#define uint unsigned int
//#define int LL
//#define double long double
#define mkp make_pair
#define par pair<int,int>
#define psb push_back
#define epb emplace_back
#define f(x) ((x).first)
#define s(x) ((x).second)
using namespace std;
#define Lbt(x) ((x)&(-(x)))
#define Swap(x,y) (x^=y^=x^=y)
const int Mxxx=1e5;
inline char gc()
{
//	return getchar();
	static char buf[Mxxx],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxxx,stdin),p1==p2)?EOF:*p1++;
}
inline char pc(char ch,bool fl=false)
{
//	return fl?0:putchar(ch),0;
	static char buf[Mxxx],*p1=buf,*p2=buf+Mxxx;
	return (fl||((*p1++=ch)&&p1==p2))&&(fwrite(buf,1,p1-buf,stdout),p1=buf),0;
}
#define output pc('!',true)
inline int read()
{
	char ch=gc();
	int gans=0,gflag=0;
	for(;ch<'0'||'9'<ch;gflag|=ch=='-',ch=gc());
	for(;'0'<=ch&&ch<='9';gans=(gans<<1)+(gans<<3)+(ch^48),ch=gc());
	return gflag?-gans:gans;
}
template<typename T>
inline char read(T&gans)
{
	char ch=gc();
	int gflag=0;gans=0;
	for(;ch<'0'||'9'<ch;gflag|=ch=='-',ch=gc());
	for(;'0'<=ch&&ch<='9';gans=(gans<<1)+(gans<<3)+(ch^48),ch=gc());
	return gans=gflag?-gans:gans,ch;
}
template<typename T>
inline void write(T x)
{
	if(x>9)write(x/10);
	pc(x%10^48);
}
template<typename T>
inline void writenum(T x,char ch)
{
	if(x<0)pc('-'),x=-x;
	write(x);pc(ch);
}
inline void writechar(char x,char ch)
{
	pc(x);pc(ch);
}
template<typename T>
inline T Max(T x,T y)
{
	return x>y?x:y;
}
template<typename T>
inline T Min(T x,T y)
{
	return x<y?x:y;
}
template<typename T>
inline T Abs(T x)
{
	return x<0?-x:x;
}
template<typename T>
inline void ckmx(T&x,T y)
{
	x=Max(x,y);
}
template<typename T>
inline void ckmn(T&x,T y)
{
	x=Min(x,y);
}
const int Mx=3e5;
int n,cnt,h[Mx+5],nxt[Mx+5],tto[Mx+5];
inline void ade(int x,int y)
{
	nxt[++cnt]=h[x];
	tto[h[x]=cnt]=y;
}
int sz[Mx+5],sn[Mx+5],pr[Mx+5],dp[Mx+5],tp[Mx+5];
inline void DFS(int x,int y,int z)
{
	int i,to;sz[x]=1;pr[x]=y;dp[x]=z;
	for(i=h[x];i;i=nxt[i])
	{
		DFS(to=tto[i],x,z+1);
		if(sz[sn[x]]<sz[to])sn[x]=to;
		sz[x]+=sz[to];
	}
}
inline void DFS(int x,int y)
{
	int i,to;tp[x]=y;if(sn[x])DFS(sn[x],y);
	for(i=h[x];i;i=nxt[i])if((to=tto[i])^sn[x])DFS(to,to);
}
int num,blg[Mx+5];
int rd[Mx+5];vector<int>vec[Mx+5];
inline void Upd(int x)
{
	if(blg[x]^num)blg[x]=num,rd[x]=0,vec[x].clear();
}
const int M=5e5;
int top,stk[M+5];
inline void Add(int x,int y)
{
	Upd(x);Upd(y);vec[x].epb(y);rd[y]++;stk[++top]=x;
}
inline void Slv(int x,int y)
{
	int xx=tp[x],yy=tp[y],lsx=x,lsy=y;int f=0;
	for(;xx^yy;)
	{
		if(dp[xx]<dp[yy])Swap(x,y),Swap(xx,yy),Swap(lsx,lsy),f^=1;
		xx=tp[x=pr[lsx=xx]];
	}
	if(dp[x]<dp[y])Swap(x,y),Swap(lsx,lsy),f^=1;
	if(x^y)lsx=sn[y];
	if(f)Add(lsy,lsx);else Add(lsx,lsy);
}
queue<int>q;int vis[Mx+5];
inline int Tp()
{
	int i,x;
	for(i=1;i<=top;i++)if(!rd[x=stk[i]]&&vis[x]^num)q.push(x),vis[x]=num;
	for(;!q.empty();)
	{
		x=q.front();q.pop();
		for(int to:vec[x])if(!(--rd[to])&&vis[to]^num)q.push(to),vis[to]=num;
	}
	for(i=1;i<=top;i++)if(rd[stk[i]])return 0;
	return 1;
}
int Q,s[M+5];
signed main()
{
	#ifndef ONLINE_JUDGE
	freopen("_.in","r",stdin);
//	freopen("_.out","w",stdout);
	#endif
	int i,j,k,t,f;n=read();
	for(i=2;i<=n;i++)ade(read(),i);
	DFS(1,0,1);DFS(1,1);
	for(Q=read();Q;Q--)
	{
		t=read();top=0;num++;
		for(i=1;i<=t;i++)s[i]=read();
		for(f=i=1;i<=t;i=j)
		{
			for(j=i;j<=t&&dp[s[i]]==dp[s[j]];j++);
			if(j<=t)f&=dp[s[i]]<dp[s[j]];
			for(k=i;k<j-1;k++)Slv(s[k],s[k+1]);
		}
		puts(f&&Tp()?"Yes":"No");
	}
	return output;
}
/*
6
1 1 3 2 4
1 2 1 1
*/
/*
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
*/

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 23944kb

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: 0
Accepted
time: 46ms
memory: 31488kb

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:

ok 254 token(s): yes count is 89, no count is 165

Test #3:

score: 0
Accepted
time: 42ms
memory: 30628kb

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:

Yes
No
No
Yes
No
No
Yes
Yes
No
Yes
No
Yes
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
Yes
No
No
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
No
No
No
Yes
No
No
Yes
No
Yes
Yes
No
No
No
Yes
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
No
No
No
Yes
No
...

result:

ok 266 token(s): yes count is 102, no count is 164

Test #4:

score: 0
Accepted
time: 45ms
memory: 32352kb

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

result:

ok 252 token(s): yes count is 87, no count is 165

Test #5:

score: 0
Accepted
time: 0ms
memory: 24396kb

input:

10
1 1 3 3 1 3 1 3 9
10000
4 3 5 6 9
5 3 1 4 9 6
5 6 4 3 5 7
28 8 3 4 3 1 6 3 5 8 7 2 4 4 4 2 7 5 9 2 4 10 8 4 10 3 4 5 7
3 5 2 9
6 4 7 2 3 9 5
5 9 2 5 6 1
12 3 5 8 8 1 3 5 8 4 5 9 1
29 3 9 9 1 5 8 5 5 6 10 8 8 4 8 4 2 8 10 5 7 3 7 1 8 4 7 5 1 6
7 5 9 8 3 2 1 6
4 4 1 9 5
22 10 9 5 4 5 8 10 3 2 1 10 ...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
...

result:

ok 10000 token(s): yes count is 1058, no count is 8942

Test #6:

score: 0
Accepted
time: 0ms
memory: 22136kb

input:

9
1 2 1 2 2 4 2 6
10000
6 5 1 4 3 7 8
14 6 8 7 9 7 5 1 8 3 6 3 8 5 2
2 6 9
17 7 8 6 5 2 1 5 5 9 3 4 1 5 2 7 2 5
3 8 6 5
5 3 9 1 6 8
8 3 5 8 7 9 4 6 2
4 8 9 6 5
7 4 7 2 9 3 8 1
6 1 4 9 5 6 2
4 7 5 4 3
5 9 5 2 1 3
4 4 5 7 3
3 9 1 8
4 4 2 8 6
26 7 4 7 6 1 7 9 4 5 5 8 9 8 2 4 8 9 6 2 8 6 4 5 5 4 4
45 3 ...

output:

No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
N...

result:

ok 10000 token(s): yes count is 1492, no count is 8508

Test #7:

score: 0
Accepted
time: 6ms
memory: 24192kb

input:

8
1 1 2 4 2 4 6
10000
5 2 6 6 2 1
3 7 3 8
2 8 1
5 7 5 1 2 7
3 2 3 5
3 8 4 3
5 8 2 4 5 3
4 3 2 1 8
6 6 8 4 5 3 1
6 3 1 2 7 4 6
4 8 6 4 3
5 4 7 6 8 5
11 2 1 6 5 2 7 1 3 3 5 4
4 6 1 7 2
7 6 2 7 8 4 1 3
3 4 6 7
3 7 1 6
38 3 4 6 6 3 4 8 1 5 3 1 8 8 6 2 3 6 7 8 8 4 2 3 7 3 3 6 7 7 5 7 5 8 8 5 4 5 7
1 8
5 ...

output:

No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
...

result:

ok 10000 token(s): yes count is 1568, no count is 8432

Test #8:

score: 0
Accepted
time: 3ms
memory: 24280kb

input:

7
1 2 3 1 2 5
10000
5 1 7 3 5 6
5 5 3 2 7 4
4 5 2 6 4
12 3 1 5 5 6 6 3 5 3 5 3 3
11 2 3 2 6 7 3 6 6 3 3 3
2 3 2
6 1 3 4 2 6 7
3 2 7 1
6 5 2 7 3 4 1
27 2 5 6 1 7 1 7 1 4 6 7 1 6 2 1 7 1 3 4 4 7 7 2 6 4 4 3
2 5 6
1 7
3 3 1 4
4 1 7 3 4
3 4 2 1
4 4 1 6 7
4 6 2 7 4
4 5 1 6 4
1 3
5 1 2 3 5 7
5 2 3 7 6 5
1...

output:

No
No
Yes
No
No
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
No
Yes
No
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
No
Yes
Yes
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Ye...

result:

ok 10000 token(s): yes count is 2205, no count is 7795

Extra Test:

score: 0
Extra Test Passed