QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#48470#4387. Static Query on Treezzxzzx123WA 349ms70704kbC++174.9kb2022-09-13 22:13:012022-09-13 22:13:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-13 22:13:02]
  • 评测
  • 测评结果:WA
  • 用时:349ms
  • 内存:70704kb
  • [2022-09-13 22:13:01]
  • 提交

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'