QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#57797#4387. Static Query on TreeqinjianbinWA 214ms40312kbC++173.3kb2022-10-22 23:03:382022-10-22 23:03:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-22 23:03:39]
  • 评测
  • 测评结果:WA
  • 用时:214ms
  • 内存:40312kb
  • [2022-10-22 23:03:38]
  • 提交

answer

#include <bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 2e5 + 10;
int ta[N << 2], tab[N << 2], tabc[N << 2];
int lazya[N << 2], lazyb[N << 2], lazyc[N << 2];
int d[N], fa[N], top[N], id[N], siz[N], son[N], cnt;
vector<int> g[N];
vector<pair<int, int>> A, B, C;
int n, q;

void dfs1(int u, int father)
{
	d[u] = d[father] + 1;
	fa[u] = father;
	siz[u] = 1;
	for(int v: g[u])
	{
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[son[u]] < siz[v]) son[u] = v;
	}
}

void dfs2(int u, int fa, int t)
{
	top[u] = t;
	id[u] = ++cnt;
	
	if(siz[u] == 1) return;
	dfs2(son[u], u, t);

	for(int v: g[u])
	{
		if(v == fa || v == son[u]) continue;
		dfs2(v, u, v);
	}
}

void add(int u, int v, int op)
{
	while(top[u] != top[v])
	{
		if(d[top[u]] < d[top[v]]) swap(u, v);
		if(!op) A.push_back({id[top[u]], id[u]});
		else B.push_back({id[top[u]], id[u]});
		u = fa[top[u]];
	}
	if(d[u] < d[v]) swap(u, v);
	if(!op) A.push_back({id[v], id[u]});
	else B.push_back({id[v], id[u]});
}

void updateA(int k, int l, int r)
{
	ta[k] = r - l + 1;
	lazya[k] = 1;
}

void updateB(int k, int l, int r)
{
	tab[k] = ta[k];
	lazyb[k] = 1;
}

void updateC(int k, int l, int r)
{
	tabc[k] = tab[k];
	lazyc[k] = 1;
}

void up(int k)
{
	ta[k] = ta[l(k)] + ta[r(k)];
	tab[k] = tab[l(k)] + tab[r(k)];
	tabc[k] = tabc[l(k)] + tabc[r(k)];
}

void down(int k, int l, int r)
{
	int m = l + r >> 1;
	if(lazya[k]) updateA(l(k), l, m), updateA(r(k), m + 1, r), lazya[k] = 0; 
	if(lazyb[k]) updateB(l(k), l, m), updateB(r(k), m + 1, r), lazyb[k] = 0; 
	if(lazyc[k]) updateC(l(k), l, m), updateC(r(k), m + 1, r), lazyc[k] = 0; 
}

void change(int k, int l, int r, int L, int R, int op)
{
	if(L <= l && r <= R)
	{
		if(!op) updateA(k, l, r);
		else if(op == 1) updateB(k, l, r);
		else updateC(k, l, r);
		return;
	}
	down(k, l, r);
	int m = l + r >> 1;
	if(L <= m) change(l(k), l, m, L, R, op);
	if(R > m) change(r(k), m + 1, r, L, R, op);
	up(k);
}

void Clear(int k, int l, int r, int L, int R)
{
	if(L <= l && r <= R)
	{
		ta[k] = tab[k] = tabc[k] = lazya[k] = lazyb[k] = lazyc[k] = 0;
		return;
	}
	int m = l + r >> 1;
	if(L <= m) Clear(l(k), l, m, L, R);
	if(R > m) Clear(r(k), m + 1, r, L, R);
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d", &n, &q);
		_for(i, 1, n) g[i].clear(), son[i] = d[i] = top[i] = fa[i] = id[i] = 0;
		cnt = 0;
		_for(i, 2, n)
		{
			int x; scanf("%d", &x);
			g[x].push_back(i);
		}

		dfs1(1, 0);
		dfs2(1, 0, 1);

		while(q--)
		{
			A.clear(); B.clear(); C.clear();

			int na, nb, nc, x;
			scanf("%d%d%d", &na, &nb, &nc);
			while(na--)
			{
				scanf("%d", &x);
				add(1, x, 0);
			}
			while(nb--)
			{
				scanf("%d", &x);
				add(1, x, 1);
			}
			while(nc--)
			{
				scanf("%d", &x);
				C.push_back({id[x], id[x] + siz[x] - 1});
			}

			for(auto [l, r]: A) change(1, 1, n, l, r, 0);
			for(auto [l, r]: B) change(1, 1, n, l, r, 1);
			for(auto [l, r]: C) change(1, 1, n, l, r, 2);
			printf("%d\n", tabc[1]);

			for(auto [l, r]: A) Clear(1, 1, n, l, r);
			for(auto [l, r]: B) Clear(1, 1, n, l, r);
			for(auto [l, r]: C) Clear(1, 1, n, l, r);
		}
	}

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 214ms
memory: 40312kb

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:

102147
63740
88657
90321
69548
73441
74895
89095
75187
75952
78208
65566
53640
89408
77988
56678
56721
82422
91429
51525
50581
73274
97996
87086
73792
74097
83587
93195
81638
81635
88383
76680
96760
71443
97712
89958
90866
65871
87862
93553
93499
93712
96845
96836
96832
82899
72719
81355
68758
44008...

result:

wrong answer 2nd numbers differ - expected: '62590', found: '63740'