QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#419563 | #8720. BFS 序 0 | wcdr | WA | 41ms | 29316kb | C++17 | 4.0kb | 2024-05-24 02:32:45 | 2024-05-24 02:32:46 |
Judging History
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();
}
int top,stk[Mx+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;
inline int Tp()
{
int i,x;
for(i=1;i<=top;i++)if(!rd[stk[i]])q.push(stk[i]);
for(;!q.empty();)
{
x=q.front();q.pop();
for(int to:vec[x])if(!(--rd[to]))q.push(to);
}
for(i=1;i<=top;i++)if(rd[stk[i]])return 0;
return 1;
}
int Q,s[Mx+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
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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 22072kb
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: 41ms
memory: 29316kb
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 No No 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 No Yes Yes No No Yes No No No No No Yes Yes No No No No No No No No Yes No No No Yes No No Yes No No Yes No Yes No No No Yes No ...
result:
wrong answer expected YES, found NO [3rd token]