QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#57803 | #4387. Static Query on Tree | qinjianbin | WA | 250ms | 40528kb | C++17 | 3.4kb | 2022-10-22 23:19:19 | 2022-10-22 23:19:30 |
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;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'