QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#340505#4387. Static Query on Treecrsfaa#WA 88ms47572kbC++144.0kb2024-02-29 09:22:152024-02-29 09:22:15

Judging History

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

  • [2024-02-29 09:22:15]
  • 评测
  • 测评结果:WA
  • 用时:88ms
  • 内存:47572kb
  • [2024-02-29 09:22:15]
  • 提交

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'