QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#57803#4387. Static Query on TreeqinjianbinWA 250ms40528kbC++173.4kb2022-10-22 23:19:192022-10-22 23:19:30

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:19:30]
  • 评测
  • 测评结果:WA
  • 用时:250ms
  • 内存:40528kb
  • [2022-10-22 23:19:19]
  • 提交

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;
	}
	down(k, l, r);
	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;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 250ms
memory: 40528kb

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
82022
85915
81448
89095
75187
76599
78801
73256
62158
90993
79243
60504
60544
84202
93333
51525
50581
73277
97999
88622
75329
76598
84554
94765
84166
84162
89392
77690
96769
73046
97713
90431
94717
69723
94340
96675
96621
96624
96846
96837
96833
82899
82974
81355
73540
47501...

result:

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