QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105269#5020. 举办乘凉州喵,举办乘凉州谢谢喵bashkort#0 840ms377660kbC++206.1kb2023-05-13 20:25:342024-05-26 02:53:49

Judging History

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

  • [2024-05-26 02:53:49]
  • 评测
  • 测评结果:0
  • 用时:840ms
  • 内存:377660kb
  • [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:25:34]
  • 提交

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]);
        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 (!isp(path[j][t ^ 1], path[j][t]) && leader(path[j][t ^ 1]) == v) {
                    cout << "here!" << endl;
                    //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);
        }

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

    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: 10ms
memory: 33972kb

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:

here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
...

result:

wrong output format Expected integer, but "here!" found

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 597ms
memory: 371712kb

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: 840ms
memory: 377660kb

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:

here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
here!
...

result:

wrong output format Expected integer, but "here!" found

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%