QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#48470 | #4387. Static Query on Tree | zzxzzx123 | WA | 349ms | 70704kb | C++17 | 4.9kb | 2022-09-13 22:13:01 | 2022-09-13 22:13:02 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 50;
int T, n, q, A, B, C, stk[N<<2], tp, vis[N<<2];
vector<int> g[N];
int top[N], son[N], id[N], siz[N], fa[N], dep[N], idx;
struct node {
int l, r, dp[8], lazy;
node () {
lazy = 0;
memset (dp, 0, sizeof (int) * 8);
dp[0] = 1;
}
node (int le, int ri): l(le), r(ri) {
lazy = 0;
memset (dp, 0, sizeof (int) * 8);
dp[0] = 1;
}
}t[N << 2];
#define ls (x << 1)
#define rs (x << 1 | 1)
void dfs (int u, int p) {
siz[u] = 1, fa[u] = p, dep[u] = dep[p] + 1;
for (int v : g[u]) {
if (v == p) continue;
dfs (v, u);
siz[u] += siz[v];
if (siz[son[u]] < siz[v]) son[u] = v;
}
}
void dfs2 (int u, int tt) {
top[u] = tt, id[u] = ++ idx;
if (! son[u]) return ;
dfs2 (son[u], tt);
for (int v : g[u]) {
if (v == fa[u] || v == son[u]) continue;
dfs2 (v, v);
}
}
void pushdown (int x, int v) {
if (! vis[x]) stk[++ tp] = x, vis[x] = true;
int f[8];
memcpy (f, t[x].dp, sizeof (int) * 8);
for (int i = 0; i < 8; i ++) t[x].dp[i] = 0;
for (int i = 0; i < 8; i ++) t[x].dp[i | v] += f[i];
t[x].lazy |= v;
}
void pushdown (int x) {
if (t[x].lazy) {
t[ls].lazy |= t[x].lazy;
t[rs].lazy |= t[x].lazy;
if (! vis[ls]) stk[++ tp] = ls, vis[ls] = true;
if (! vis[rs]) stk[++ tp] = rs, vis[rs] = true;
int f[8];
memcpy (f, t[ls].dp, sizeof (int) * 8);
for (int i = 0; i < 8; i ++) t[ls].dp[i] = 0;
for (int i = 0; i < 8; i ++) t[ls].dp[i | t[x].lazy] += f[i];
memcpy (f, t[rs].dp, sizeof (int) * 8);
for (int i = 0; i < 8; i ++) t[rs].dp[i] = 0;
for (int i = 0; i < 8; i ++) t[rs].dp[i | t[x].lazy] += f[i];
t[x].lazy = 0;
}
}
void pushup (int x) {
if (! vis[x]) stk[++ tp] = x, vis[x] = true;
for (int i = 0; i < 8; i ++)
t[x].dp[i] = t[ls].dp[i] + t[rs].dp[i];
}
void build (int l, int r, int x = 1) {
t[x] = node ();
t[x].l = l, t[x].r = r;
if (l == r) return ;
int mid = (l + r) >> 1;
build (l, mid, ls), build (mid + 1, r, rs);
pushup (x);
// cerr << t[x].l << ' ' << t[x].r << ' ' << t[x].dp[0] << endl;
}
void update (int l, int r, int v, int x = 1) {
if (l <= t[x].l && t[x].r <= r) {
pushdown (x, v);
return ;
}
pushdown (x);
int mid = (t[x].l + t[x].r) >> 1;
if (l <= mid) update (l, r, v, ls);
if (r > mid) update (l, r, v, rs);
pushup (x);
}
void update_path (int u, int v, int c) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap (u, v);
update (id[top[u]], id[u], c);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap (u, v);
update (id[v], id[u], c);
}
void print (int x = 1) {
if (t[x].l == t[x].r) {
cerr << t[x].l << endl;
for (int i = 0; i < 8; i ++)
cerr << t[x].dp[i] << ' ';
cerr << endl;
return ;
}
print (ls), print (rs);
}
int main() {
#ifdef LOCAL
clock_t c1 = clock();
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
// ===================================================
scanf ("%d", &T);
while (T --) {
scanf ("%d%d", &n, &q);
for (int i = 1; i <= n; i ++) g[i].clear ();
dep[1] = 0, idx = 0, tp = 0;
memset (son, 0, sizeof (son));
memset (vis, 0, sizeof (vis));
for (int i = 2; i <= n; i ++) {
int x; scanf ("%d", &x);
g[i].push_back (x);
g[x].push_back (i);
}
dfs (1, 1);
dfs2 (1, 1);
build (1, n);
// printf("%d\n", t[1].dp[7]);
while (q --) {
scanf ("%d%d%d", &A, &B, &C);
for (int i = 1; i <= A; i ++) {
int x; scanf ("%d", &x);
update_path (x, 1, 1);
}
for (int i = 1; i <= B; i ++) {
int x; scanf ("%d", &x);
update_path (x, 1, 2);
}
for (int i = 1; i <= C; i ++) {
int x; scanf ("%d", &x);
update (id[x], id[x] + siz[x] - 1, 4);
}
printf ("%d\n", t[1].dp[7]);
// if (q == 0) print ();
// cerr << "stk = " << endl;
while (tp) {
// cerr << stk[tp] << ' ';
vis[stk[tp]] = false;
int lef = t[stk[tp]].l, rig = t[stk[tp]].r;
t[stk[tp]] = node (lef, rig), tp --;
}
// cerr << endl;
// build (1, n);
}
}
// ===================================================
#ifdef LOCAL
cerr << "Time Used: " << clock() - c1 << "ms" << endl;
#endif
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 349ms
memory: 70704kb
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 42 61 24 17 62 73 10 82 47 33 77 15 58 55 7 8 7 77 25 34 21 69 21 11 52 58 65 59 57 38 32 25 18 42 52 7 18 26 44 88 9 45 52 59 6 19 34 25 18 47 20 61 64 52 31 32 24 75 5 33 79 48 5 35 33 18 39 33 6 58 52 49 47 35 30 57 21 7 50 78 48 25 9 73 55 8 36 3 25 66 75 45 7 18 73 50 37 7 21 10 47 49 39...
result:
wrong answer 2nd numbers differ - expected: '62590', found: '42'