QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127799#5020. 举办乘凉州喵,举办乘凉州谢谢喵pandapythoner0 499ms124460kbC++207.5kb2023-07-20 05:49:582023-07-20 05:50:01

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:50:01]
  • 评测
  • 测评结果:0
  • 用时:499ms
  • 内存:124460kb
  • [2023-07-20 05:49:58]
  • 提交

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


*/

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: 5952kb

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
1075
4971
12
1676
3619
5520
4783
19
82
5837
4084
203
5010
437
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
4400
508
4891
398
4060
1907
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: 284ms
memory: 61540kb

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
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 499ms
memory: 124460kb

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
107137
146159
5625
109830
196600
3767
90633
75
12997
149
58
707
209932
25
214767
491
216614
152523
9582
141771
184639
99
187595
70360
462
168847
126672
102926
282
191665
710
142
161509
2648
18643
131812
202928
2388
145457
181739
214113
13638
45356
71512
187518
114467
636
131
2108
220332
159872
19...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%