QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#105275#5020. 举办乘凉州喵,举办乘凉州谢谢喵bashkort0 1926ms400632kbC++206.1kb2023-05-13 20:28:232023-05-13 20:28:27

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-13 20:28:27]
  • 评测
  • 测评结果:0
  • 用时:1926ms
  • 内存:400632kb
  • [2023-05-13 20:28:23]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct SegmentTree {
    SegmentTree *left = nullptr, *right = nullptr;
    int sum = 0, lx = 0, rx = 0;

    SegmentTree(int l, int r) {
        sum = 0, lx = l, rx = r;
    }

    void modify(int i, int d) {
        sum += d;

        if (lx + 1 == rx) {
            return;
        }

        int mid = lx + rx >> 1;
        if (i < mid) {
            if (!left) {
                left = new SegmentTree(lx, mid);
            }
            left->modify(i, d);
        } else {
            if (!right) {
                right = new SegmentTree(mid, rx);
            }
            right->modify(i, d);
        }
    }

    int rangeSum(int l, int r) {
        if (l >= r || lx >= r || l >= rx) {
            return 0;
        }
        if (l <= lx && rx <= r) {
            return sum;
        }
        return (left ? left->rangeSum(l, r) : 0) + (right ? right->rangeSum(l, r) : 0);
    }
};

constexpr int N = 2e5 + 1;

vector<int> adj[N], subVertices[N], dying[N];
vector<pair<int, int>> subQueries[N], born[N]; //id, 0/1
SegmentTree *V[N], *A[N], *D[N];
set<int> mda[N];


int path[N][2], type[N];
ll answer[N];
int deadDepth[N], dist[N], LCA[N];

int depth[N], jump[N], tin[N], tout[N], parent[N], n, fa[N];

int isp(int x, int y) {
    return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int leader(int x) {
    while (x != fa[x]) {
        x = fa[x] = fa[fa[x]];
    }
    return x;
}

void dfsInit(int v) {
    static int T = 0;
    tin[v] = T++;

    for (int to : adj[v]) {
        adj[to].erase(find(adj[to].begin(), adj[to].end(), v));
        depth[to] = depth[v] + 1;
        parent[to] = v;

        int p = jump[v], pp = jump[p];
        if (depth[pp] - depth[p] == depth[p] - depth[v]) {
            jump[to] = pp;
        } else {
            jump[to] = v;
        }

        dfsInit(to);
    }

    tout[v] = T;
}

int lca(int x, int y) {
    while (!isp(x, y)) {
        if (!isp(jump[x], y)) {
            x = jump[x];
        } else {
            x = parent[x];
        }
    }
    return x;
}

void dfs(int v) {
    for (int &to : adj[v]) {
        dfs(to);
        if (subQueries[to].size() + subVertices[to].size() > subQueries[adj[v][0]].size() + subVertices[adj[v][0]].size()) {
            swap(adj[v][0], to);
        }
    }

    if (!adj[v].empty()) {
        int x = adj[v][0];
        swap(V[v], V[x]), swap(A[v], A[x]), swap(D[v], D[x]);
        swap(subQueries[v], subQueries[x]), swap(subVertices[x], subVertices[x]);
        swap(mda[v], mda[x]);
        fa[x] = v;
    } else {
        V[v] = new SegmentTree(0, n);
        A[v] = new SegmentTree(0, n);
        D[v] = new SegmentTree(-n, n);
    }

    auto insertVertex = [&](int u) {
        A[v]->modify(depth[u] - depth[v], 1);
        D[v]->modify(depth[v] - (depth[u] - depth[v]), 1);
        V[v]->modify(depth[u], 1);
        subVertices[v].push_back(u);
    };

    insertVertex(v);

    for (int i = 1; i < adj[v].size(); ++i) {
        int to = adj[v][i];

        for (int u : subVertices[to]) {
            A[v]->modify(depth[u] - depth[v], 1);
            D[v]->modify(depth[v] - (depth[u] - depth[v]), 1);
        }

        for (auto [j, t] : subQueries[to]) {
            if (type[j] == 0) {
                if (mda[v].count(j)) {
                    //already added his friend
                    continue;
                }
                //alive
                answer[j] += A[to]->rangeSum(0, dist[j] + 1);
                answer[j] += V[v]->rangeSum(depth[v], depth[v] + dist[j] + 1);
                answer[j] -= A[v]->rangeSum(0, dist[j] + 1);
            } else {
                //dead
                answer[j] += D[to]->rangeSum(deadDepth[j], n);
                answer[j] += V[v]->rangeSum(depth[v], depth[v] + (dist[j] - (depth[LCA[j]] - depth[v])) + 1);
                answer[j] -= D[v]->rangeSum(deadDepth[j], n);
            }
        }

        for (int u : subVertices[to]) {
            subVertices[v].push_back(u);
            V[v]->modify(depth[u], 1);
        }
        for (int j : mda[to]) {
            mda[v].insert(j);
        }
        mda[to].clear();

        fa[to] = v;
        subQueries[v].insert(subQueries[v].end(), subQueries[to].begin(), subQueries[to].end());
        subQueries[to].clear(), subVertices[to].clear();
    }

    for (auto [j, t] : born[v]) {
        //alive
        answer[j] += V[v]->rangeSum(depth[v], depth[v] + dist[j] + 1);
        answer[j] -= A[v]->rangeSum(0, dist[j] + 1);
        mda[v].insert(j);
    }

    subQueries[v].insert(subQueries[v].end(), born[v].begin(), born[v].end());

    for (int j : dying[v]) {
        answer[j] += A[v]->rangeSum(0, dist[j] + 1);
        answer[j] -= D[v]->rangeSum(deadDepth[j], n);
        type[j] = 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    iota(fa, fa + N, 0);

    cin >> n;

    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        a -= 1, b -= 1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfsInit(0);

    int q;
    cin >> q;

    for (int i = 0; i < q; ++i) {
        cin >> path[i][0] >> path[i][1] >> dist[i];
        path[i][0] -= 1, path[i][1] -= 1;

        LCA[i] = lca(path[i][0], path[i][1]);
        deadDepth[i] = depth[LCA[i]] - dist[i];

        if (isp(path[i][1], path[i][0])) {
            swap(path[i][1], path[i][0]);
        }

        born[path[i][1]].emplace_back(i, 1);

        if (!isp(path[i][0], path[i][1])) {
            born[path[i][0]].emplace_back(i, 0);
        }

        dying[LCA[i]].push_back(i);

//        cout << path[i][0] << " " << path[i][1] << " " << LCA[i] << " " << deadDepth[i] << endl;
    }

    dfs(0);

    for (auto [j, t] : subQueries[0]) {
        if (type[j] == 0) {
            answer[j] += A[0]->rangeSum(0, dist[j] + 1);
        } else {
            answer[j] += D[0]->rangeSum(deadDepth[j], n);
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << answer[i] << '\n';
    }

    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 27ms
memory: 44220kb

input:

4988
1 2
1 3
1 4
4 5
1 6
3 7
3 8
5 9
4 10
6 11
3 12
9 13
11 14
8 15
11 16
1 17
7 18
8 19
18 20
7 21
10 22
15 23
18 24
4 25
24 26
9 27
23 28
3 29
3 30
30 31
11 32
18 33
2 34
32 35
29 36
29 37
19 38
9 39
6 40
25 41
16 42
31 43
6 44
42 45
32 46
27 47
32 48
44 49
7 50
10 51
24 52
46 53
30 54
46 55
39 56...

output:

738
635
692
342
311
674
678
676
780
631
367
396
760
381
812
903
685
798
805
143
672
769
699
748
150
210
692
842
282
711
467
754
578
766
349
756
646
287
200
852
740
186
209
822
770
524
686
740
229
427
203
308
297
678
731
683
216
703
297
182
753
443
695
435
749
859
146
706
180
879
743
209
624
470
299
...

result:

wrong answer 1st numbers differ - expected: '3226', found: '738'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 1247ms
memory: 382160kb

input:

199995
1 2
2 3
2 4
1 5
3 6
5 7
6 8
4 9
2 10
5 11
5 12
1 13
1 14
1 15
13 16
1 17
10 18
16 19
11 20
8 21
17 22
4 23
19 24
7 25
22 26
8 27
14 28
1 29
9 30
3 31
3 32
21 33
19 34
26 35
34 36
5 37
29 38
22 39
5 40
13 41
28 42
8 43
35 44
22 45
14 46
12 47
32 48
11 49
8 50
18 51
23 52
18 53
4 54
6 55
10 56
...

output:

336
3703
629
4908
4106
99
3834
4962
1810
3048
2575
4398
139
326
14
2397
31
3553
3729
34
3766
4372
4250
823
384
51
3223
3416
4634
3838
4125
85
1
6
4
3
3
11
3394
4768
4540
4297
4448
3436
3604
4118
3997
186
4499
3680
1180
24
3835
3920
4910
3119
2113
707
29
94
2972
158
3849
1931
40
784
1
39
4722
4163
84...

result:

wrong answer 1st numbers differ - expected: '757', found: '336'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 1926ms
memory: 400632kb

input:

199991
1 2
2 3
3 4
3 5
5 6
3 7
1 8
8 9
8 10
10 11
1 12
1 13
13 14
4 15
12 16
13 17
17 18
8 19
3 20
9 21
16 22
10 23
1 24
7 25
6 26
12 27
4 28
21 29
27 30
30 31
21 32
19 33
20 34
17 35
7 36
13 37
24 38
37 39
30 40
31 41
15 42
9 43
32 44
41 45
18 46
38 47
8 48
35 49
13 50
35 51
47 52
35 53
48 54
44 55...

output:

1276
5839
7152
3782
6562
6219
2322
5896
283
4833
1334
250
1810
6619
1081
6134
1679
5966
7214
4705
7389
5974
762
6877
5889
1740
7840
7848
7045
421
6475
1688
1327
7347
2754
5407
7407
8036
2691
6198
7735
6588
4936
6525
6094
6077
5975
1799
1114
2482
6051
5881
5102
6642
6245
2317
6984
7042
1341
6455
7547...

result:

wrong answer 1st numbers differ - expected: '78', found: '1276'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%