QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61988#4387. Static Query on Treeluyiming123TL 0ms0kbC++143.9kb2022-11-16 15:46:422022-11-16 15:46:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-16 15:46:46]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-11-16 15:46:42]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int Test,n,q;
int NA,NB,NC;
vector <int> g[N];
int siz[N],top[N],dfn[N],son[N],dep[N],f[N],dfntot = 0;
struct node
{
	int val[3],tag[3];
}T[N << 2];
void pushup(int root)
{
	for(int i = 0; i <= 2; i++) 
		T[root].val[i] = T[root << 1].val[i] + T[root << 1 | 1].val[i];
	return;
}
void build(int root,int l,int r,int opt)
{
	T[root].val[opt] = T[root].tag[opt] = 0;
	if(l == r) 
	{
		return;
	}
	int mid = (l + r) >> 1;
	build(root << 1, l,mid,opt),build(root << 1 | 1, mid + 1,r,opt);
	return;
}
void pushdown(int root,int l,int r,int opt)
{
	if(T[root].tag[opt] == 0) return; int tag = T[root].tag[opt],mid = (l + r) >> 1;
	T[root << 1].val[opt] += tag * (mid - l + 1),T[root << 1 | 1].val[opt] += tag * (r - mid);
	T[root << 1].tag[opt] += tag,T[root << 1 | 1].tag[opt] += tag;
	T[root].tag[opt] = 0;
	return;
}
void update(int root,int l,int r,int s,int t,int d,int opt)
{
	if(l <= s && t <= r) 
	{
		T[root].val[opt] += d * (t - s + 1),T[root].tag[opt] += d;
		return;
	}
	pushdown(root,s,t,opt);
	int mid = (s + t) >> 1;
	if(l <= mid) update(root << 1,l,r,s,mid,d,opt);
	if(r > mid) update(root << 1 | 1,l,r,mid + 1,t,d,opt);
	pushup(root); return;
}
int query(int root,int l,int r,int x,int opt)
{
	if(l == r) return T[root].val[opt];
	pushdown(root,l,r,opt);
	int mid = (l + r) >> 1;
	int ans = 0;
	if(x <= mid) ans += query(root << 1,l,mid,x,opt);
	else ans += query(root << 1 | 1,mid + 1,r,x,opt);
	return ans;
}
void dfs1(int x,int fa)
{
	siz[x] = 1,f[x] = fa,dep[x] = dep[fa] + 1;
	for(int i = 0; i < (int)g[x].size(); i++)
	{
		int v = g[x][i];
		if(v == fa) continue;
		dfs1(v,x);
		siz[x] += siz[v]; 
		if(son[x] == 0 || siz[v] > siz[son[x]]) son[x] = v;
	}
	return;
}
void dfs2(int x,int t)
{
	top[x] = t;
	dfn[x] = ++dfntot;
	if(son[x]) dfs2(son[x],t);
	for(int i = 0; i < (int)g[x].size(); i++)
	{
		int v = g[x][i];
		if(v == f[x] || v == son[x]) continue;
		dfs2(v,v);
	}
	return;
}
void Modify_Path(int x,int y,int d,int opt)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] > dep[top[y]]) swap(x,y);
		update(1,dfn[top[y]],dfn[y],1,dfntot,d,opt),y = f[top[y]];
	}
	if(dfn[x] > dfn[y]) swap(x,y); 
	update(1,dfn[x],dfn[y],1,dfntot,d,opt);
	return;
}
void Modify_Subtree(int x,int d,int opt)
{
	update(1,dfn[x],dfn[x] + siz[x] - 1,1,dfntot,d,opt); return;
}
int main(void)
{	
	scanf("%d",&Test);
	while(Test--)
	{
		scanf("%d%d",&n,&q);
		for(int i = 1; i <= n; i++) g[i].clear();
		for(int i = 2; i <= n; i++)
		{
			int f; scanf("%d",&f);
			g[f].push_back(i),g[i].push_back(f);
		}
		
		dfs1(1,0),dfs2(1,1);
		for(int i = 0; i < 3; i++) build(1,1,dfntot,i);
//		for(int i = 1; i <= n; i++) 
//			fprintf(stderr,"dep[%d] = %d,dfn[%d] = %d,siz[%d] = %d,top[%d] = %d,son[%d] = %d\n",i,dep[i],i,dfn[i],i,siz[i],i,top[i],i,son[i]);
		while(q--)
		{
			scanf("%d%d%d",&NA,&NB,&NC);
			vector <pair<int,int> > OptA,OptB;
			for(int i = 1; i <= NA; i++) 
			{
				int x; scanf("%d",&x);
//				fprintf(stderr,"MP: i = %d\n",i);
				Modify_Path(1,x,1,0); OptA.push_back({x,0});
//				fprintf(stderr,"Final.\n");
			}
			for(int i = 1; i <= NB; i++)
			{
				int x; scanf("%d",&x);
				Modify_Path(1,x,1,1); OptA.push_back({x,1});
			}
			for(int i = 1; i <= NC; i++)
			{
				int x; scanf("%d",&x);
				Modify_Subtree(x,1,2); OptB.push_back({x,2});
			}
			int total = 0;
			for(int i = 1; i <= n; i++) 
			{
				int x = query(1,1,dfntot,dfn[i],0),y = query(1,1,dfntot,dfn[i],1),z = query(1,1,dfntot,dfn[i],2);
//				printf("i = %d,x = %d,y = %d,z = %d\n",i,x,y,z);
				if(x && y && z) ++total;
			}
			printf("%d\n",total);
			for(int i = 0; i < (int)OptA.size(); i++) Modify_Path(1,OptA[i].first,-1,OptA[i].second);
			for(int i = 0; i < (int)OptB.size(); i++) Modify_Subtree(OptB[i].first,-1,OptB[i].second);
		}
	}
	return 0;
}

详细

Test #1:

score: 0
Time Limit Exceeded

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:


result: