QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253507#7626. Quake and Rebuilducup-team2307WA 121ms3956kbC++204.6kb2023-11-17 04:06:362023-11-17 04:06:37

Judging History

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

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2023-11-17 04:06:37]
  • 评测
  • 测评结果:WA
  • 用时:121ms
  • 内存:3956kb
  • [2023-11-17 04:06:36]
  • 提交

answer

#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int B = 512;

struct DSU {
    vector<int> e;
    DSU(int n) : e(n, -1) {}
    int find(int v) { return e[v] < 0 ? v : e[v] = find(e[v]); }
    void join(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return;
        if(u < v) swap(u, v);
        e[u] += e[v];
        e[v] = u;
    }
};

struct Tree {
    int n;
    vector<int> a, ba, up, up_len;
    DSU jump;
    Tree(int n) : n(n), a(n), ba(n / B + 1), up(n), up_len(n), jump(n + 1) {}

    inline int get_par(int x) {
        return max(0, a[x] + ba[x / B]);
    }

    inline array<int, 2> get_up(int p) {
        int par = get_par(p);
        if(p / B != par / B)
            return {par, 1};
        return {up[p], up_len[p]};
    }

    void read() {
        up[0] = 0;
        up_len[0] = 0;
        for(int i = 1; i < n; i++) {
            cin >> a[i], a[i]--;
            if((a[i] / B) != (i / B))
                up[i] = a[i], up_len[i] = 1;
            else {
                auto [x, y] = get_up(a[i]);
                up[i] = x;
                up_len[i] = 1 + y;
            }
        }
    }

    inline void sub(int l, int r, int x) {
        int p = l;
        while(l <= r && (l & (B - 1)))
            a[l++] -= x;
        for(; l + B - 1 <= r; l += B)
            ba[l / B] -= x;
        while(l <= r)
            a[l++] -= x;

        for(p = jump.find(p); p <= r; p = jump.find(p + 1)) {
            int par = get_par(p);
            if((p / B) != (par / B)) {
                jump.join(p, p + 1);
            } else {
                auto [x, y] = get_up(par);
                up[p] = x;
                up_len[p] = 1 + y;
            }
        }
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    Tree T(n);
    T.read();

    vector<vector<int>> ch(n);
    vector<int> to_clear, vis(n);
    int sum, lca = n;
    auto clear = [&]() {
        sum = 1;//to account for root
        for(auto i : to_clear) {
            vis[i] = 0;
            ch[i].clear();
        }
        to_clear = { 0 };
    };
    auto crawl = [&](int v, int slow) {
        int add = 0, chi = -1;
        // cout << v << " -->\n";
        while(!vis[v]++ && v) {
            if(!slow && chi != -1) {
                ch[v].push_back(chi);
            }
            chi = v;

            vis[v] = 1;
            to_clear.push_back(v);
            if(slow) {
                v = T.get_par(v);
                add++;
            } else {
                auto [x, y] = T.get_up(v);
                v = x;
                add += y;
            }
        }
        // cout << v << " " << add << " yay" << endl;
        if(!slow && chi != -1) {
            ch[v].push_back(chi);
        }
        return add;
    };
    auto correct = [&](int v) {
        int add = 1;
        while(v) {
            auto [x, y] = T.get_up(v);
            if(vis[v] >= 2)
                add = 0;
            else
                add += y;
            v = x;
        }
        if(vis[v] >= 2) add = 0;
        // cout << add << endl;
        return add;
    };

    for(int t, qi = 0; qi < m; qi++) {
        cin >> t;
        if(t == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            // cout << 1 << " " << l << " " << r << " " << x << endl;
            --l, --r;
            T.sub(l, r, x);
        } else {
            int k;
            cin >> k;
            vector<int> V(k);
            for(auto &i : V) cin >> i, i--;

            clear();
            for(auto i : V)
                sum += crawl(i, 0);

            // cout << sum << " -\n";
            for(int rel = to_clear.size(), i = 0; i < rel; i++) {
                int UP = to_clear[i];
                // if(ch[UP].size() > 1)
                // cout << UP << " " << ch[UP].size() << endl;
                for(auto p : ch[UP]) {
                    sum -= T.get_up(p)[1] - 1;
                    int U = crawl(T.get_par(p), 1);
                    // cout << UP << " -> " << p << " " << T.get_par(p) << " " << (T.get_up(p)[1] - 1) << " | " << U << endl;
                    sum += U;
                }
                vis[UP] -= ch[UP].size();
            }
            // cout << sum << " - ";
            
            int lca = 0;
            for(auto i : to_clear) if(vis[i] == 1)
                lca = max(lca, i);
            sum -= correct(V[0]);
            cout << sum << '\n';
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 5
1 2 2
2 2 1 4
1 2 3 1
2 3 2 3 4
1 4 4 1
2 2 3 4

output:

3
4
3

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

10 10
1 2 3 3 4 5 7 7 9
1 2 10 3
2 9 9 5 3 10 7 2 4 6 8
1 6 10 3
1 2 7 3
1 7 10 3
2 2 4 3
2 3 7 4 4
1 3 9 3
1 3 9 3
1 10 10 3

output:

10
3
3

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 121ms
memory: 3708kb

input:

3051 198219
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...

output:

78
78
70
64
60
55
60
58
52
54
51
53
56
51
51
57
55
52
49
55
49
50
53
49
49
48
49
48
53
50
50
54
47
52
45
49
49
46
47
48
49
50
48
49
47
48
47
49
48
50
48
49
48
47
49
48
51
48
48
45
45
46
50
50
50
48
49
46
47
47
46
48
48
47
49
47
46
47
46
47
46
45
47
49
49
50
51
48
48
49
47
47
48
50
46
47
48
50
46
47
...

result:

ok 13214 lines

Test #4:

score: -100
Wrong Answer
time: 96ms
memory: 3956kb

input:

6173 198631
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 99 ...

output:

2693
1318
1476
1026
1039
5984
267
977
773
887
421
835
171
43
46
593
538
669
567
6046
6087
414
5
352
36
357
6036
374
6136
372
271
83
323
343
34
344
321
6102
5831
277
317
198
273
347
215
6100
16
13
5447
172
7
42
240
204
234
10
24
28
212
198
213
212
218
180
178
235
28
198
136
35
185
24
215
15
197
191
6...

result:

wrong answer 1st lines differ - expected: '2819', found: '2693'