QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#340505 | #4387. Static Query on Tree | crsfaa# | WA | 88ms | 47572kb | C++14 | 4.0kb | 2024-02-29 09:22:15 | 2024-02-29 09:22:15 |
Judging History
answer
#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s;
}
const int mxn=6e5+5;
struct node
{
int x,nxt;
}a[mxn*2];
int head[mxn];
int cnt;
void add(int x,int y)
{
a[++cnt].x=y;
a[cnt].nxt=head[x];
head[x]=cnt;
}
int f[mxn];
int dcnt;
#define pr pair<int,int>
struct Word_RMQ
{
#define w 32
#define u unsigned
#define be(x) ((x>>5)+1)
#define l(x) ((x-1<<5)+(x==1))
#define r(x) min(N,((x<<5)-1))
#define bm mxn/w+5
int N;
pr *a;
pr ST[int(log2(bm)+1)][bm];
pr pre[mxn],nxt[mxn];
struct node
{
u st[w+1];
pr *p;
inline pr ask(int l,int r)
{
return p[l+__builtin_ctz(st[r]>>l-1)];
}
void init(pr *p_,int len)
{
p=p_;
int i,top=0;
int stack[w+1];
for(i=1;i<=len;i++)
{
st[i]=st[i-1];
while(top&&p[i]<p[stack[top]])
st[i]-=1u<<stack[top--]-1;
stack[++top]=i,st[i]+=1u<<i-1;
}
}
}k[bm];
void build(pr A[],int n)
{
a=A,N=n;
int i,j,cnt=0;
for(i=1;;i++)
{
k[i].init(a+l(i)-1,r(i)-l(i)+1);
for(j=l(i)+1,pre[l(i)]=a[l(i)];j<=r(i);j++)
pre[j]=min(pre[j-1],a[j]);
for(j=r(i)-1,nxt[r(i)]=a[r(i)];j>=l(i);j--)
nxt[j]=min(nxt[j+1],a[j]);
ST[0][i]=pre[r(i)];
cnt++;
if(r(i)==n) break;
}
for(j=1;(1<<j)<=cnt;j++)
for(i=1;i+(1<<j)-1<=cnt;i++)
ST[j][i]=min(ST[j-1][i],ST[j-1][i+(1<<(j-1))]);
}
inline pr STask(int L,int R)
{
if(L>R) return make_pair(INT_MAX,INT_MAX);
int k=__lg(R-L+1);
return min(ST[k][L],ST[k][R-(1<<k)+1]);
}
inline pr ask(int L,int R)
{
if(L>R) return make_pair(INT_MAX,INT_MAX);
if(be(L)==be(R)) return k[be(L)].ask(L-l(be(L))+1,R-l(be(L))+1);
return min({STask(be(L)+1,be(R)-1),pre[R],nxt[L]});
}
#undef w
#undef l
#undef r
}ds;
pr st[mxn];
int dep[mxn];
void dfs(int d,int deep,int fa)
{
st[dcnt]=make_pair(dep[d]=deep,fa),f[d]=++dcnt;
for(int i=head[d];i;i=a[i].nxt)
if(!f[a[i].x])
dfs(a[i].x,deep+1,d);
}
int asklca(int l,int r)
{
if(l==r) return l;
l=f[l],r=f[r];
if(l>r) swap(l,r);
return ds.ask(l,r-1).second;
}
int ca[mxn],cb[mxn],cc[mxn];
int ht[mxn],fa[mxn];
vector<int> h[mxn];
int sum;
bool cmp(int x,int y)
{
return f[x]<f[y];
}
void dfs(int d,int s)
{
s+=cc[d];
for(auto i:h[d])
dfs(i,s),ca[d]+=ca[i],cb[d]+=cb[i];
if(ca[d]&&cb[d])
sum+=!!s+(dep[d]-dep[fa[d]]-1)*(s>1);
}
int main()
{
int T=read();
while(T--)
{
int n=read(),m=read(),x,i;
cnt=dcnt=0;
memset(head,0,n+1<<2);
for(i=2;i<=n;i++)
add(read(),i);
dfs(1,1,0);
ds.build(st,n);
while(m--)
{
int sz1=read(),sz2=read(),sz3=read(),cnt=0;
ht[++cnt]=1;
while(sz1--)
x=ht[++cnt]=read(),ca[x]=1;
while(sz2--)
x=ht[++cnt]=read(),cb[x]=1;
while(sz3--)
x=ht[++cnt]=read(),cc[x]=1;
sort(ht+1,ht+1+cnt,cmp);
cnt=unique(ht+1,ht+1+cnt)-ht-1;
for(i=cnt;i>1;i--)
ht[++cnt]=asklca(ht[i],ht[i-1]);
sort(ht+1,ht+1+cnt,cmp);
cnt=unique(ht+1,ht+1+cnt)-ht-1;
for(i=2;i<=cnt;i++)
h[fa[ht[i]]=asklca(ht[i],ht[i-1])].push_back(ht[i]);
sum=0,dfs(1,0);
printf("%d\n",sum);
for(i=1;i<=cnt;i++)
h[ht[i]].clear(),ca[ht[i]]=cb[ht[i]]=cc[ht[i]]=0;
}
}
}
/*
2
7 3
1 1 2 2 3 3
2 1 1
1 2
4
1
4 4 3
4 5 6 7
4 5 6 7
2 4 6
2 1 1
4 5
6
1
7 3
1 1 2 2 3 3
2 1 1
1 2
4
1
4 4 3
4 5 6 7
4 5 6 7
2 4 6
2 1 1
4 5
6
1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 88ms
memory: 47572kb
input:
1 200000 18309 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
output:
102146 5 6 3 3 7 7 2 8 5 4 7 3 6 6 2 2 2 7 3 4 3 7 3 2 5 6 6 6 6 4 4 3 3 5 5 2 3 3 5 8 2 5 5 6 2 3 4 3 3 5 3 6 6 5 5 4 3 7 2 4 7 5 2 4 4 3 4 4 2 7 5 5 5 4 4 5 3 2 5 8 5 4 2 7 6 2 4 2 3 6 7 5 2 3 7 5 4 2 3 2 5 5 5 5 7 4 4 3 5 5 2 5 2 2 6 2 5 4 8 4 3 4 6 2 6 3 8 3 4 2 3 6 3 5 4 7 4 4 5 6 4 2 3 5 6 3 3...
result:
wrong answer 1st numbers differ - expected: '102147', found: '102146'