QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105265#5020. 举办乘凉州喵,举办乘凉州谢谢喵bashkort#0 720ms361024kbC++205.9kb2023-05-13 20:13:432024-05-26 02:53:44

Judging History

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

  • [2024-05-26 02:53:44]
  • 评测
  • 测评结果:0
  • 用时:720ms
  • 内存:361024kb
  • [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:13:43]
  • 提交

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];
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]);
        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 (!isp(path[j][t ^ 1], path[j][t]) && 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);
//        cout << "born: " << j << " " << t << endl;
    }

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

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 29108kb

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:

49
32
47
20
33
45
42
42
58
30
25
29
56
32
48
67
41
53
64
14
45
53
46
49
21
24
48
57
20
49
37
54
43
46
33
60
47
30
21
59
53
14
25
69
55
32
44
48
22
37
20
24
28
46
50
51
19
46
33
14
52
30
47
32
52
48
17
53
26
65
55
22
38
28
20
33
45
43
71
45
51
40
35
34
69
36
34
46
19
45
16
64
63
45
9
51
65
40
72
49
1...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 444ms
memory: 355116kb

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:

33
50
29
64
52
16
69
82
39
46
39
53
27
25
9
49
10
42
51
11
43
50
56
40
22
7
28
33
64
63
41
20
1
5
4
3
3
7
46
88
79
68
67
26
58
70
51
29
64
42
45
11
55
46
85
44
37
32
9
17
53
23
59
43
14
40
1
14
71
60
26
29
11
27
57
55
13
13
18
38
21
71
54
49
53
19
56
20
3
60
13
9
79
62
78
5
11
12
17
38
48
27
68
5
58...

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 720ms
memory: 361024kb

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:

22
74
101
61
91
116
68
70
24
79
32
23
47
122
27
94
38
89
109
62
120
94
31
101
78
42
129
119
97
25
122
48
36
118
58
87
105
135
57
101
112
135
63
74
100
79
84
46
38
46
105
78
68
107
95
51
90
95
28
120
102
51
77
110
157
83
76
80
101
136
58
118
129
119
102
96
114
111
83
137
82
75
59
30
148
97
36
65
44
6...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%