QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#57806 | #4387. Static Query on Tree | qinjianbin | WA | 225ms | 40356kb | C++17 | 3.3kb | 2022-10-22 23:23:41 | 2022-10-22 23:23:42 |
Judging History
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] = siz[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: 225ms
memory: 40356kb
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'