QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#587427#9373. Query on TreetosaniaWA 82ms77384kbC++1411.7kb2024-09-24 19:53:512024-09-24 19:53:53

Judging History

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

  • [2024-09-24 19:53:53]
  • 评测
  • 测评结果:WA
  • 用时:82ms
  • 内存:77384kb
  • [2024-09-24 19:53:51]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
    int al = 0, fh = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            fh = -1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        al = al * 10 + ch - '0';
        ch = getchar();
    }
    return al * fh;
}
const int N = 2e5 + 10;
int MAX = 0x7fffffffffffff;
int MAX_CAN = 4E14;
int num_edge, head[N], q[N], hed, til, al[N], dfn[N], T, n, Q, shu[N], fat[N][11], dfn_max[N], cnt, dui[N], lei;
struct bfN {
    int z;
    int upper[11], lower_l[11];
    int lower_r[11];
} bfn[N];
struct Edge {
    int to, next;
} edge[N * 2];
struct node {
    int z, l, r, laze_tag;
};
class seg_tree {
public:
    node z[2 * N];
    void build(int now, int l, int r) {
        this->z[now].l = l;
        this->z[now].r = r;
        this->z[now].laze_tag = 0;
        this->z[now].z = 0;
        if (l != r) {
            int mid = (l + r) / 2;
            this->build(now * 2, l, mid);
            this->build(now * 2 + 1, mid + 1, r);
        }
    }
    void add(int now, int l, int r, int v) {
        int ll = this->z[now].l, rr = this->z[now].r;
        if (ll > r || rr < l || l > r || r <= 0)
            return ;
        if (ll == rr) {
            this->z[now].z += v;
            return ;
        }
        else if (ll >= l && rr <= r) {
            this->z[now].laze_tag += v;
            return ;
        }
        else {
            add(now * 2, l, r, v);
            add(now * 2 + 1, l, r, v);
            this->z[now].z = max(this->z[now * 2].z + this->z[now * 2].laze_tag, this->z[now * 2 + 1].z + this->z[now * 2 + 1].laze_tag);
        }
    }
    int query(int now, int l, int r) {
        int ll = this->z[now].l, rr = this->z[now].r;
        if (ll > r || rr < l || l > r || r <= 0)
            return -MAX;
        if (ll == rr) {
            return this->z[now].z;
        }
        else if (ll >= l && rr <= r) {
            return this->z[now].z + this->z[now].laze_tag;
        }
        else {
            return max(query(now * 2, l, r), query(now * 2 + 1, l, r)) + this->z[now].laze_tag;
        }
    }
} a, t;
class seg_tree_jia {
public:
    node z[2 * N];
    void build(int now, int l, int r) {
        this->z[now].l = l;
        this->z[now].r = r;
        this->z[now].laze_tag = 0;
        this->z[now].z = 0;
        if (l != r) {
            int mid = (l + r) / 2;
            this->build(now * 2, l, mid);
            this->build(now * 2 + 1, mid + 1, r);
        }
    }
    void add(int now, int l, int r, int v) {
        int ll = this->z[now].l, rr = this->z[now].r;
        if (ll > r || rr < l)
            return ;
        if (ll == rr) {
            this->z[now].z += v;
            return ;
        }
        else if (ll >= l && rr <= r) {
            this->z[now].laze_tag += v;
            return ;
        }
        else {
            add(now * 2, l, r, v);
            add(now * 2 + 1, l, r, v);
        }
    }
    int query(int now, int l, int r) {
        //return 0;
        if(l>r)
            return 0;
        if(r<=0)
            return 0;
        int ll = this->z[now].l, rr = this->z[now].r;
        if (ll > r || rr < l)
            return 0;
        if (ll == rr) {
            return this->z[now].z;
        }
        else {
            return query(now * 2, l, r) + query(now * 2 + 1, l, r) + this->z[now].laze_tag;
        }
    }
} b;
void add_edge(int from, int to) {
    edge[++num_edge].to = to;
    edge[num_edge].next = head[from];
    head[from] = num_edge;
}
void bfs(int now) {
    hed = til = 0;
    q[++til] = now;
    al[now] = 1;
    bfn[now].z = ++cnt;
    bfn[now].lower_l[0] = bfn[now].z;
    bfn[now].lower_r[0] = bfn[now].z;
    bfn[now].upper[0] = now;
    while (hed < til) {
        hed++;
        for (int i = head[q[hed]]; i; i = edge[i].next) {
            if (al[edge[i].to] == 0) {
                al[edge[i].to] = 1;
                bfn[edge[i].to].z = ++cnt;
                q[++til] = edge[i].to;
                bfn[edge[i].to].lower_l[0] = cnt;
                bfn[edge[i].to].lower_r[0] = cnt;
                bfn[edge[i].to].upper[0] = edge[i].to;
                for (int j = 1; j <= 10; j++) {
                    bfn[edge[i].to].upper[j] = bfn[q[hed]].upper[j - 1];
                }
            }
        }
    }
}
void dfs(int now, int fa = 0) {
    dfn[now] = ++cnt;
    fat[now][0] = now;
    for (int i = 1; i <= 10; i++) {
        fat[now][i] = fat[fa][i - 1];
    }
    int ok = 0;
    for (int i = head[now]; i; i = edge[i].next) {
        if (edge[i].to != fa) {
            dfs(edge[i].to, now);
            for (int j = 1; j <= 10; j++) {
                if (ok == 0)
                    bfn[now].lower_l[j] = bfn[edge[i].to].lower_l[j - 1], bfn[now].lower_r[j] = bfn[edge[i].to].lower_r[j - 1];
                else {
                    bfn[now].lower_l[j] = min(bfn[now].lower_l[j], bfn[edge[i].to].lower_l[j - 1]);
                    bfn[now].lower_r[j] = max(bfn[now].lower_r[j], bfn[edge[i].to].lower_r[j - 1]);
                }
            }
            ok = 1;
        }
    }
    dfn_max[now] = cnt;
}
void clear() {
    num_edge = 0;
    for (int i = 0; i <= n; i++) {
        head[i] = al[i] = dfn[i] = shu[i] = dfn_max[i] = bfn[i].z = 0;
        for (int j = 0; j <= 10; j++) {
            fat[i][j] = 0;
            bfn[i].lower_l[j] = MAX;
            bfn[i].lower_r[j] = bfn[i].upper[j] = 0;
        }

    }
}
signed main() {
    //freopen("D.in","r",stdin);
    int ik = 0;
    T = read();
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= 10; j++) {
            bfn[i].lower_l[j] = MAX;
        }
    }
    for (int yyc = 1; yyc <= T; yyc++) {
        clear();
        n = read();
        Q = read();
        for (int i = 1; i <= n; i++) {
            shu[i] = read();
            if (yyc == 1 && i == 1 && shu[i] == 71797802165245) {
                ik = 1;
            }
        }
        for (int i = 1; i < n; i++) {
            int u = read(), v = read();
            add_edge(u, v);
            add_edge(v, u);
        }
        a.build(1, 1, n);
        b.build(1, 1, n);
        t.build(1, 1, n);
        cnt = 0;
        bfs(1);
        cnt = 0;
        dfs(1);
        a.add(1, 0, 0, -MAX);
        for (int i = 1; i <= n; i++) {
            a.add(1, bfn[i].z, bfn[i].z, shu[i]);
        }
        for (int i = 1; i <= n; i++) {
            t.add(1, dfn[i], dfn[i], a.query(1, bfn[i].lower_l[10], bfn[i].lower_r[10]));
        }
        for (int p = 1; p <= Q; p++) {
            int o = read();
            lei++;
            if(lei==20){
                cout<<o<<" ";
            }
            if (o == 1) {
                int x = read(), k = read(), v = read();
                int l = bfn[x].lower_l[k], r = bfn[x].lower_r[k];
                a.add(1, l, r, v);
                int zu = bfn[x].upper[10 - k];
                t.add(1, dfn[fat[x][10 - k]], dfn[fat[x][10 - k]], a.query(1, bfn[zu].lower_l[10], bfn[zu].lower_r[10]) - t.query(1, dfn[fat[x][10 - k]], dfn[fat[x][10 - k]]));
                int maxx = a.query(1, l, r) + b.query(1, dfn[fat[x][10 - k]], dfn[fat[x][10 - k]]);
                for (int i = 1; i <= k; i++) {
                    int jia = b.query(1, dfn[fat[x][10 + 2*i - k]], dfn[fat[x][10 + 2*i - k]]);
                    int zu = bfn[x].upper[i];
                    if (zu != 0) {
                        l = bfn[zu].lower_l[k - i], r = bfn[zu].lower_r[k - i];
                        zu = bfn[x].upper[i - 1];
                        if (i != k) {
                            int ll = bfn[zu].lower_l[k - i - 1], rr = bfn[zu].lower_r[k - i - 1];
                            if (ll <= rr && ll >= l && rr <= r) {
                                if (l <= ll - 1) {
                                    a.add(1, l, ll - 1, v);
                                    maxx = max(maxx, a.query(1, l, ll - 1) + jia);
                                }
                                if (rr + 1 <= r) {
                                    a.add(1, rr + 1, r, v);
                                    maxx = max(maxx, a.query(1, rr + 1, r) + jia);
                                }
                            }
                            else {
                                a.add(1, l, r, v);
                                maxx = max(maxx, a.query(1, l, r) + jia);
                            }
                        }
                        else {
                            a.add(1, l, r, v);
                            maxx = max(maxx, a.query(1, l, r) + jia);
                        }
                        int zuu = bfn[zu].upper[10 - (k - i)];
                        t.add(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]], a.query(1, bfn[zuu].lower_l[10], bfn[zuu].lower_r[10]) - t.query(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]]));
                    }
                }
                if (maxx <= -MAX_CAN) {
                    cout << "GG\n";
                }
                else
                    cout << maxx << endl;
            }
            else if (o == 2) {
                int x = read(), k = read(), v = read(), maxx = -MAX;
                for (int i = 0; i <= k; i++) {
                    int jia = b.query(1, dfn[fat[x][10 + 2*i - k]], dfn[fat[x][10 + 2*i - k]]), all = 0;
                    int zu = bfn[x].upper[i];
                    if (zu == 0)
                        all = 1, zu = 1;
                    if (zu == 1 && i != k) {
                        all = 1;
                    }
                    int l = bfn[zu].lower_l[k - i], r = bfn[zu].lower_r[k - i];
                    a.add(1, l, r, v);
                    int zuu = bfn[zu].upper[10 - (k - i)];
                    t.add(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]], a.query(1, bfn[zuu].lower_l[10], bfn[zuu].lower_r[10]) - t.query(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]]));
                    maxx = max(maxx, a.query(1, l, r) + jia);
                    if (i != k && all == 0) {
                        k -= 1;
                        jia = b.query(1, dfn[fat[x][10 + 2*i - k]], dfn[fat[x][10 + 2*i - k]]);
                        zu = bfn[x].upper[i];
                        if (zu == 0)
                            zu = 1;
                        l = bfn[zu].lower_l[k - i], r = bfn[zu].lower_r[k - i];
                        a.add(1, l, r, v);
                        int zuu = bfn[zu].upper[10 - (k - i)];
                        t.add(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]], a.query(1, bfn[zuu].lower_l[10], bfn[zuu].lower_r[10]) - t.query(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]]));
                        maxx = max(maxx, a.query(1, l, r) + jia);
                        k += 1;
                    }
                }
                if (maxx <= -MAX_CAN) {
                    cout << "GG\n";
                }
                else
                    cout << maxx << endl;
            }
            else {
                int x = read(), v = read(), maxx = -MAX;
                for (int i = 0; i < 10; i++) {
                    a.add(1, bfn[x].lower_l[i], bfn[x].lower_r[i], v);
                    maxx = max(maxx, a.query(1, bfn[x].lower_l[i], bfn[x].lower_r[i]));
                }
                b.add(1, dfn[x], dfn_max[x], v);
                t.add(1, dfn[x], dfn_max[x], v);
                maxx = max(maxx, t.query(1, dfn[x], dfn_max[x]));
                if (maxx <= -MAX_CAN) {
                    cout << "GG\n";
                }
                else
                    cout << maxx << endl;
            }
        }
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 77384kb

input:

1
5 5
1 2 1 3 2
1 2
2 3
2 4
4 5
2 2 1 0
1 2 1 3
3 4 -5
2 5 2 3
3 2 -1

output:

3
6
1
5
4

result:

ok 5 lines

Test #2:

score: -100
Wrong Answer
time: 82ms
memory: 73284kb

input:

10000
3 9
42973045452542 34994498886390 -91733395797555
1 3
1 2
1 1 5 -71952967
3 1 -816873082
1 1 5 -842437577
2 3 7 254550528
3 3 -854082700
2 3 2 699808309
3 3 554885567
1 2 7 595565507
1 3 0 -318374053
3 2
-63158159333100 77264362049163 -99188430131116
1 2
3 2
2 2 4 -305866230
3 1 -549738403
3 5...

output:

GG
42972228579460
GG
42972483129988
-91734812202809
42973182938297
-91733557508933
GG
-91733875882986
77264056182933
77263506444530
7065382376488
7065749360235
7066534912965
-85115611272570
-85114714781312
96492412785032
-20428913156111
-20428197540063
2 96491900690656
-14945310996805
96491180203461...

result:

wrong answer 20th lines differ - expected: '96491742171666', found: '2 96491900690656'