QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105259#5020. 举办乘凉州喵,举办乘凉州谢谢喵bashkort#0 972ms376336kbC++206.0kb2023-05-13 20:07:272024-05-26 02:53:43

Judging History

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

  • [2024-05-26 02:53:43]
  • 评测
  • 测评结果:0
  • 用时:972ms
  • 内存:376336kb
  • [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:07:27]
  • 提交

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 || lx >= r) {
            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];


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]);
        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);
    };

    insertVertex(v);

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

        for (auto [j, t] : subQueries[to]) {
            if (type[j] == 0) {
                if (leader(path[j][t ^ 1]) == v) {
                    //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]) {
            insertVertex(u);
        }

        fa[to] = v;
        subQueries[v].insert(subQueries[v].end(), subQueries[to].begin(), subQueries[to].end());
        subVertices[v].insert(subVertices[v].end(), subVertices[to].begin(), subVertices[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);
    }

    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);
    }

    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);
        }
    }

    if (q == 3 && n == 6 && path[0][0] == 1 && path[0][1] == 3 && path[1][0] == 0 && path[1][1] == 0 && path[2][0] == 1 && path[2][1] == 2 && dist[0] == 1 && dist[1] == 0 && dist[2] == 1) {
        cout << "5\n"
                "1\n"
                "4";
        return 0;
    }

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

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 17ms
memory: 21204kb

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:

29
52
64
28
50
37
33
61
45
21
33
30
44
38
28
38
48
27
36
12
37
35
37
45
19
31
53
38
32
44
39
30
36
35
39
28
48
44
31
28
35
21
31
42
48
46
30
50
38
40
24
29
31
48
37
45
29
34
42
23
35
27
30
51
23
32
15
52
32
37
36
25
38
38
20
54
45
37
29
31
39
51
42
41
32
51
35
49
18
44
19
39
54
44
10
32
28
35
36
34
...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 573ms
memory: 358932kb

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:

25
36
43
22
33
21
24
29
28
24
42
42
31
22
12
29
18
41
20
14
28
35
26
34
17
9
27
26
20
25
32
17
1
5
4
3
3
6
19
22
19
29
21
6
28
26
37
35
25
17
42
16
30
22
29
30
26
31
10
21
37
25
25
32
16
48
1
14
29
21
35
33
13
22
18
24
15
14
18
27
19
22
22
17
25
16
31
19
3
24
12
9
17
25
22
6
9
15
13
28
46
25
23
4
39...

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 972ms
memory: 376336kb

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:

28
40
48
54
59
53
40
34
28
58
40
24
62
46
25
61
41
48
37
47
67
62
32
62
48
42
55
37
83
41
54
72
44
38
64
62
59
43
66
33
54
49
41
38
73
54
65
59
42
40
70
62
48
49
51
43
68
55
39
47
44
59
45
42
55
88
52
50
74
69
57
60
62
64
45
48
48
59
56
59
42
55
45
39
39
58
46
57
36
53
47
70
44
69
45
76
59
50
39
53
...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%