QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#602601 | #8720. BFS 序 0 | Kanate# | WA | 376ms | 88344kb | C++14 | 2.4kb | 2024-10-01 11:07:18 | 2024-10-01 11:07:18 |
Judging History
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];
int q,m,a[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;
}
void solve()
{
assign(1,n,1);
read(m);
rep(i,1,m)read(a[i]);
rep(i,1,m-1)
if(dep[a[i]]>dep[a[i+1]])
{puts("No");return;}
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)
{
int fa;read(fa);
g[fa].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: 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:
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: 376ms
memory: 88344kb
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 Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
wrong answer expected NO, found YES [1st token]