QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127800#5020. 举办乘凉州喵，举办乘凉州谢谢喵pandapythoner0 558ms125188kbC++207.6kb2023-07-20 05:52:032023-07-20 05:52:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-20 05:52:07]
  • 评测
  • 测评结果：0
  • 用时：558ms
  • 内存：125188kb
查看
  • [2023-07-20 05:52:03]
  • 提交

answer

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(234);
const ll inf = 1e18;

struct Fenwick {
    int n;
    vector<int> t;

    void build(int _n) {
        n = _n;
        t.assign(n + 1, 0);
    }

    void add(int i) {
        i += 1;
        if (i <= 0 || i > n) {
            assert(0);
        }
        while (i <= n) {
            t[i] += 1;
            i = (i | (i - 1)) + 1;
        }
    }

    int get(int r) {
        r += 1;
        if (r <= 0) {
            return 0;
        }
        r = min(r, n);
        int rs = 0;
        while (r > 0) {
            rs += t[r];
            r = (r & (r - 1));
        }
        return rs;
    }
};

struct ask {
    int u, v;
    int d;
};

struct bbr {
    int d, f, i;
};

int n, q;
vector<vector<int>> g;
vector<ask> asks;
vector<int> sz;
vector<int> vmp;
vector<int> pr, ppr;
vector<int> dpth, dstx, dsty;
vector<vector<bbr>> b1, b2, b3, b4;
Fenwick f1, f2, f3;
vector<int> rs;

void dfs1(int v, int p) {
    sz[v] = 1;
    int mx_sz_i = -1;
    int mx_sz = -1;
    for (int i = 0; i < (int)g[v].size(); i += 1) {
        int to = g[v][i];
        if (to == p) {
            continue;
        }
        dfs1(to, v);
        sz[v] += sz[to];
        if (sz[to] > mx_sz) {
            mx_sz = sz[to];
            mx_sz_i = i;
        }
    }
    if (mx_sz_i != -1) {
        swap(g[v][0], g[v][mx_sz_i]);
    }
    for (int i = 0; i < (int)g[v].size(); i += 1) {
        int to = g[v][i];
        if (to == p) {
            g[v].erase(g[v].begin() + i);
            break;
        }
    }
}

void dfs2(int v, int &c) {
    vmp[v] = c;
    c++;
    for (auto to : g[v]) {
        dfs2(to, c);
    }
}

void hld_reorder() {
    sz.resize(n);
    dfs1(0, -1);
    vmp.resize(n);
    int c = 0;
    dfs2(0, c);
    vector<vector<int>> ng(n, vector<int>());
    for (int v = 0; v < n; v += 1) {
        for (auto to : g[v]) {
            ng[vmp[v]].push_back(vmp[to]);
        }
    }
    g.swap(ng);
    for (auto &a : asks) {
        a.u = vmp[a.u];
        a.v = vmp[a.v];
    }
}

void dfs3(int v, int p, int pp, int h, int y) {
    dpth[v] = h;
    pr[v] = p;
    ppr[v] = pp;
    dsty[v] = y;
    dstx[v] = 0;
    sz[v] = 1;
    for (int i = 0; i < (int)g[v].size(); i += 1) {
        int to = g[v][i];
        if (i == 0) {
            dfs3(to, v, pp, h + 1, y + 1);
            dstx[v] = dstx[to] + 1;
        } else {
            dfs3(to, v, to, h + 1, 0);
        }
        sz[v] += sz[to];
    }
}

void build() {
    hld_reorder();
    sz.resize(n);
    pr.resize(n);
    ppr.resize(n);
    dpth.resize(n);
    dstx.resize(n);
    dsty.resize(n);
    dfs3(0, -1, 0, 0, 0);
}

void dfs4(int v, int bnd, int h, int x) {
    f1.add(h);
    f2.add(h + x);
    for (auto to : g[v]) {
        if (to == bnd) {
            continue;
        }
        dfs4(to, bnd, h + 1, x);
    }
}

void dfs5(int v, int bnd, int h, int x) {
    f3.add(h + x);
    for (auto to : g[v]) {
        if (to == bnd) {
            continue;
        }
        dfs4(to, bnd, h + 1, x);
    }
}

void solve_rec(int v) {
    f1.build(sz[v]);
    f2.build(sz[v]);
    f3.build(sz[v]);
    vector<int> way;
    int u = v;
    while (1) {
        way.push_back(u);
        int bnd = -1;
        if (!g[u].empty()) {
            bnd = g[u][0];
        }
        dfs4(u, bnd, 0, dstx[u]);
        for (auto [d, f, i] : b1[u]) {
            rs[i] += f * f1.get(d);
        }
        for (auto [d, f, i] : b2[u]) {
            rs[i] += f * f2.get(d);
        }
        if (g[u].empty()) {
            break;
        }
        u = g[u][0];
    }
    reverse(all(way));
    for (auto u : way) {
        int bnd = -1;
        if (!g[u].empty()) {
            bnd = g[u][0];
        }
        dfs5(u, bnd, 0, dsty[u]);
        for (auto [d, f, i] : b3[u]) {
            rs[i] += f * f3.get(d);
        }
    }
    for (auto [d, f, i] : b4[v]) {
        rs[i] += f * f3.get(d);
    }
    u = v;
    while (1) {
        for (int i = 1; i < (int)g[u].size(); i += 1) {
            solve_rec(g[u][i]);
        }
        if (g[u].empty()) {
            break;
        }
        u = g[u][0];
    }
    // g[n + 1].push_back(0);
}

void solve() {
    rs.assign(q, 0);
    build();
    b1.assign(n, {});
    b2.assign(n, {});
    b3.assign(n, {});
    b4.assign(n, {});
    for (int i = 0; i < q; i += 1) {
        auto a = asks[i];
        auto [u, v, d] = a;
        while (ppr[u] != ppr[v]) {
            if (dpth[ppr[u]] > dpth[ppr[v]]) {
                b1[u].push_back(bbr{d, 1, i});
                if (!g[u].empty()) {
                    b3[g[u][0]].push_back(bbr{d + dsty[u], 1, i});
                }
                b4[ppr[u]].push_back(bbr{d - 1, -1, i});
                u = pr[ppr[u]];
            } else {
                b1[v].push_back(bbr{d, 1, i});
                if (!g[v].empty()) {
                    b3[g[v][0]].push_back(bbr{d + dsty[v], 1, i});
                }
                b4[ppr[v]].push_back(bbr{d - 1, -1, i});
                v = pr[ppr[v]];
            }
        }
        if (dpth[u] > dpth[v]) {
            b1[u].push_back(bbr{d, 1, i});
            if (!g[u].empty()) {
                b3[g[u][0]].push_back(bbr{d + dsty[u], 1, i});
            }
            if (v != ppr[v]) {
                b1[pr[v]].push_back(bbr{d, -1, i});
            }
            u = v;
        } else {
            b1[v].push_back(bbr{d, 1, i});
            if (!g[v].empty()) {
                b3[g[v][0]].push_back(bbr{d + dsty[v], 1, i});
            }
            if (u != ppr[u]) {
                b1[pr[u]].push_back(bbr{d, -1, i});
            }
            v = u;
        }
        int dst = 1;
        v = pr[v];
        while (v != -1) {
            if (dst > d) {
                break;
            }
            b2[v].push_back(bbr{d + dstx[v] - dst, 1, i});
            dst += (v - ppr[v] + 1);
            b4[ppr[u]].push_back(bbr{d - dst - 1, -1, i});
            v = pr[ppr[v]];
        }
    }
    solve_rec(0);
}

void stress() {
    int c = 0;
    while (1) {
        cout << ++c << "\n";
        n = rnd() % 20 + 1;
        vector<vector<int>> mg(n);
        for (int v = 1; v < n; v += 1) {
            int u = rnd() % v;
            mg[u].push_back(v);
            mg[v].push_back(u);
        }
        q = rnd() % 20 + 1;
        vector<ask> masks(q);
        for (int i = 0; i < q; i += 1) {
            int u = rnd() % n;
            int v = rnd() % n;
            int d = rnd() % n;
            masks[i] = ask{u, v, d};
        }
        g = mg;
        asks = masks;
        solve();
    }
}

int32_t main() {
    // stress();
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    g.assign(n, vector<int>());
    for (int i = 0; i < n - 1; i += 1) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> q;
    asks.resize(q);
    for (int i = 0; i < q; i += 1) {
        int u, v, d;
        cin >> u >> v >> d;
        --u;
        --v;
        asks[i] = ask{u, v, d};
    }
    solve();
    for (int i = 0; i < q; i += 1) {
        cout << rs[i] << "\n";
    }
    return 0;
}

/*
6
1 2
2 3
2 4
1 5
4 6
1
3 3 2


*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 6012kb

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:

2882
2147
5912
200
256
3979
3634
2060
5491
1597
306
342
4925
313
3636
3893
5207
1071
4971
12
1676
3619
5520
4771
19
82
5837
4084
203
5000
436
2932
649
1690
202
3497
1168
274
84
3330
3272
70
81
4286
5493
643
4793
5102
113
482
75
160
207
2202
5308
4485
100
2706
238
66
4390
508
4891
398
4060
1902
15
51...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 344ms
memory: 74952kb

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:

611
61282
2742
97072
63565
154
23813
110168
5332
12217
9935
82851
200
496
14
8874
40
32990
165393
52
38480
107232
62443
2715
715
53
29276
44825
102911
139351
49821
78
1
6
4
3
3
10
48545
113394
102823
129378
119370
94276
46760
48346
175736
425
111700
144938
3335
26
82832
108018
115752
17193
5446
1273...

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 558ms
memory: 125188kb

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:

78
107128
146159
5625
109830
196582
3762
90633
75
12997
149
58
707
209932
25
214767
491
216614
152523
9582
141771
184624
99
187595
70352
462
168814
126659
102926
282
191665
710
142
161509
2648
18634
131812
202928
2388
145457
181739
214113
13634
45356
71505
187518
114458
636
131
2108
220332
159872
19...

result:

wrong answer 2nd numbers differ - expected: '107329', found: '107128'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-12-04 20:33:50 | OpenSource Project