QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#603074 | #8720. BFS 序 0 | Kanate# | WA | 148ms | 139008kb | C++14 | 3.6kb | 2024-10-01 14:33:58 | 2024-10-01 14:33:58 |
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];
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(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: 100
Accepted
time: 7ms
memory: 32364kb
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: 148ms
memory: 139008kb
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 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 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]