QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127792#5020. 举办乘凉州喵，举办乘凉州谢谢喵pandapythoner0 294ms61636kbC++206.8kb2023-07-20 05:42:152023-07-20 05:42:18

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:42:18]
  • 评测
  • 测评结果：0
  • 用时：294ms
  • 内存：61636kb
查看
  • [2023-07-20 05:42:15]
  • 提交

answer

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

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[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});
                }
                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);
            v = pr[ppr[v]];
        }
    }
    solve_rec(0);
}

int32_t main() {
    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
Runtime Error

Test #1:

score: 0
Runtime Error

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:

result:

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 294ms
memory: 61636kb

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:

628
61292
2752
97084
63604
155
23829
110186
5337
12222
9939
82871
209
499
15
8906
40
33015
165402
56
38488
107238
62473
2719
720
53
29282
44828
102921
139357
49829
85
1
6
4
3
3
11
48550
113400
102853
129396
119390
94280
46765
48352
175740
426
111715
144941
3359
26
82857
108038
115764
17205
5464
1281...

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #25:

score: 0
Runtime Error

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:

result:

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-12-04 19:10:28 | OpenSource Project