QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#221863#7608. Cliquesucup-team1198#WA 0ms23460kbC++204.0kb2023-10-21 14:54:312023-10-21 14:54:32

Judging History

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

  • [2023-10-21 14:54:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:23460kb
  • [2023-10-21 14:54:31]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int MOD = 1e9 + 7;

int add(int a, int b) {
    if (a + b < MOD)
        return a + b;
    return a + b - MOD;
}

int sub(int a, int b) {
    if (a >= b)
        return a - b;
    return a + MOD - b;
}

int mul(int a, int b) {
    return a * 1ll * b % MOD;
}

const int MAXN = 200'200;

vector<int> G[MAXN];
int sz[MAXN];

vector<int> order;
int tin[MAXN];
int par[MAXN];
int path_id[MAXN];
int path_st[MAXN];
int depth[MAXN];

void dfs_sz(int v, int p, int w) {
    par[v] = p;
    sz[v] = 1;
    depth[v] = w;
    for (int i = 0; i < G[v].size(); ++i) {
        if (G[v][i] == p) {
            swap(G[v][i], G[v].back());
            G[v].pop_back();
            --i;
            continue;
        }
        dfs_sz(G[v][i], v, w + 1);
        sz[v] += sz[G[v][i]];
        if (sz[G[v][i]] > sz[G[v][0]])
            swap(G[v][i], G[v][0]);
    }
}

void dfs2(int v) {
    tin[v] = order.size();
    order.emplace_back(v);
    for (int u : G[v]) {
        dfs2(u);
    }
    if (G[v].empty()) {
        path_id[v] = v;
        path_st[v] = v;
    } else {
        path_id[v] = path_id[G[v][0]];
        path_st[path_id[v]] = v;
    }
}

const pair<int, int> NONE(1, 0);
const pair<int, int> MUL2(2, 1);
const pair<int, int> DIV2((MOD + 1) / 2, MOD - (MOD + 1) / 2);

struct SegTree {
    int val[(1 << 19) + 228];
    pair<int, int> mod[(1 << 19) + 228]; // x -> ax+b

    pair<int, int> combine(const pair<int, int>& old, const pair<int, int>& new_m) {
        return make_pair(new_m.first, add(mul(new_m.first, old.second), new_m.second));
    }

    void build(int v, int left, int right) {
        mod[v] = NONE;
        val[v] = 0;
        if (left + 1 == right)
            return;
        int mid = (left + right) / 2;
        build(2 * v + 1, left, mid);
        build(2 * v + 2, mid, right);
    }

    void push(int v, int left, int right) {
        if (mod[v] == NONE)
            return;
        val[v] = add(mul(val[v], mod[v].first), mul(mod[v].second, right - left));
        if (left + 1 != right) {
            mod[2 * v + 1] = combine(mod[2 * v + 1], mod[v]);
            mod[2 * v + 2] = combine(mod[2 * v + 2], mod[v]);
        }
        mod[v] = NONE;
    }

    void upd(int v, int left, int right, int x, int y, pair<int, int> d) {
        push(v, left, right);
        if (y <= left || right <= x)
            return;
        if (x <= left && right <= y) {
            mod[v] = combine(mod[v], d);
            push(v, left, right);
            return;
        }
        int mid = (left + right) / 2;
        upd(2 * v + 1, left, mid, x, y, d);
        upd(2 * v + 2, mid, right, x, y, d);
        val[v] = add(val[2 * v + 1], val[2 * v + 2]);
    }
};

SegTree tree1;
SegTree tree2;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        G[a - 1].emplace_back(b - 1);
        G[b - 1].emplace_back(a - 1);
    }
    dfs_sz(0, -1, 0);
    dfs2(0);
    tree1.build(0, 0, n);
    tree2.build(0, 0, n);
    int q;
    cin >> q;
    while (q--) {
        char c;
        int u, v;
        cin >> c >> u >> v;
        --u;
        --v;
        pair<int, int> to_upd = c == '+' ? MUL2 : DIV2;
        while (path_id[u] != path_id[v]) {
            if (depth[path_st[path_id[u]]] < depth[path_st[path_id[v]]])
                swap(u, v);
            tree1.upd(0, 0, n, tin[path_st[path_id[u]]], tin[u] + 1, to_upd);
            tree2.upd(0, 0, n, tin[path_st[path_id[u]]], tin[u] + 1, to_upd);
            u = par[path_st[path_id[u]]];
        }
        if (depth[u] < depth[v])
            swap(u, v);
        tree1.upd(0, 0, n, tin[v], tin[u] + 1, to_upd);
        tree2.upd(0, 0, n, tin[v] + 1, tin[u] + 1, to_upd);

        tree1.push(0, 0, n);
        tree2.push(0, 0, n);

        cout << sub(tree1.val[0], tree2.val[0]) << '\n';
    }
    return 0;
}

详细

Test #1:

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

input:

5
1 2
5 1
2 3
4 2
6
+ 4 5
+ 2 2
+ 1 3
- 2 2
+ 2 3
+ 4 4

output:

1
3
7
3
7
9

result:

ok 6 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 23392kb

input:

20
8 7
19 10
12 14
3 16
17 13
7 10
5 6
1 9
15 12
5 2
16 13
3 11
20 14
18 6
1 14
16 20
11 10
3 4
20 6
30
+ 10 20
+ 14 20
+ 12 17
- 14 20
- 12 17
+ 4 6
+ 8 20
+ 3 6
- 10 20
+ 2 17
+ 1 16
+ 6 10
+ 9 10
+ 5 15
+ 7 8
- 7 8
+ 2 5
+ 3 18
+ 1 20
+ 8 16
- 3 18
- 5 15
+ 4 20
+ 14 16
- 4 6
+ 8 19
+ 4 7
- 1 16
...

output:

1
3
7
3
1
3
7
15
7
8
17
35
71
34
36
34
38
73
225
431
217
139
277
203
102
118
500000149
86
162
500000085

result:

wrong answer 10th lines differ - expected: '15', found: '8'