QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105271#5020. 举办乘凉州喵,举办乘凉州谢谢喵bashkort#0 1101ms397896kbC++206.1kb2023-05-13 20:26:382024-05-26 02:53:50

Judging History

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

  • [2024-05-26 02:53:50]
  • 评测
  • 测评结果:0
  • 用时:1101ms
  • 内存:397896kb
  • [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:26:38]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 18ms
memory: 34296kb

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:

758
735
821
333
316
718
645
735
796
767
444
560
792
429
665
796
738
800
796
150
710
821
796
717
154
258
796
792
444
726
472
801
666
710
384
783
666
260
267
665
758
269
259
785
796
558
680
796
270
574
259
384
429
710
796
801
271
783
316
271
651
574
680
429
817
867
150
717
196
785
801
255
614
572
443
...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 801ms
memory: 382204kb

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: 1101ms
memory: 397896kb

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:

1456
5933
6282
4013
6558
6082
1991
6037
269
5139
1464
284
2113
6599
1096
6784
2073
6596
6293
4780
6236
5870
781
6433
5713
2012
7803
7198
6097
550
6296
1623
1469
6593
3091
5287
6400
6599
3091
6720
6539
6596
4908
5886
5719
6566
5927
2073
1159
3091
6566
6451
5545
6784
6817
2968
6072
6451
1454
6596
6451...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%