QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#137197#5020. 举办乘凉州喵,举办乘凉州谢谢喵ckiseki0 749ms197820kbC++237.5kb2023-08-10 03:48:102023-08-10 03:48:13

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 03:48:13]
  • 评测
  • 测评结果:0
  • 用时:749ms
  • 内存:197820kb
  • [2023-08-10 03:48:10]
  • 提交

answer

// An AC a day keeps the doctor away.
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
#define orange(args...) danb(#args, args)
using std::cerr;
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    ((cerr << "\e[1;32m(" << s << ") = ("), ..., (cerr << args << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I> void danb(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L) cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;

struct Centroid {
    vector<vector<int>> &g;
    vector<vector<pair<int, int&>>> qs;
    vector<int> vis, sz;
    vector<int> dis;
    Centroid(vector<vector<int>> &t_g) : g(t_g), qs(g.size()),
        vis(g.size()), sz(g.size()), dis(g.size()) {
    }
    void solve() {
        decomp(0, 0);
    }
    void add_query(int i, int d, int &a) {
        qs[i].emplace_back(d, a);
    }

    void get_size(vector<int> &s, int i) {
        s.emplace_back(i);
        vis[i] = true;
        sz[i] = 1;
        for (int j: g[i]) if (!vis[j]) {
            get_size(s, j);
            sz[i] += sz[j];
        }
    }
    void dfs(vector<int> &s, int i) {
        s.emplace_back(i);
        vis[i] = true;
        for (int j: g[i]) if (!vis[j]) {
            dis[j] = dis[i] + 1;
            dfs(s, j);
        }
    }

    void gao(const vector<int> &vtx, int coef) {
        int mx = 0;
        for (int x: vtx) mx = max(mx, dis[x]);
        vector<int> pre(mx + 1);
        for (int x: vtx) {
            pre[dis[x]] += 1;
            mx = max(mx, dis[x]);
        }
        for (int i = 1; i <= mx; i++) pre[i] += pre[i - 1];
        for (int x: vtx) {
            for (auto &[d, p]: qs[x]) {
                // #{ y | dis[x] + dis[y] <= d }
                int cnt = d - dis[x] < 0 ? 0 : pre[min(mx, d - dis[x])];
                p += coef * cnt;
            }
        }
    }

    void decomp(int i, int d) {
        vector<int> s;
        get_size(s, i);
        int c = -1;
        for (int j: s) {
            if (sz[j] * 2 >= sz[i])
                c = j;
            vis[j] = false;
        }
        vis[c] = true;

        vector<int> total;
        vector<vector<int>> sub;
        for (int j: g[c]) {
            if (vis[j]) continue;
            dis[j] = 1;
            sub.emplace_back();
            dfs(sub.back(), j);
            for (int x: sub.back())
                total.emplace_back(x);
        }
        dis[c] = 0;
        total.emplace_back(c);

        gao(total, 1);
        for (const auto &t: sub) gao(t, -1);

        for (int j: s) vis[j] = false;
        vis[c] = true;
        for (int j: g[c]) {
            if (vis[j]) continue;
            decomp(j, d + 1);
        }
    }
};

struct HLD {
    vector<vector<int>> &g;
    vector<vector<tuple<int, int, int&>>> g_qs;
    vector<vector<tuple<int, int, int&>>> f_qs;

    vector<int> vis, sz, mxs, top, pa, dep;
    int dfc;
    vector<int> tin, tou, ord;
    int64_t totsum;
    vector<int> sum;
    HLD(vector<vector<int>> &t_g) : g(t_g),
        g_qs(g.size()), f_qs(g.size()),
        vis(g.size()), sz(g.size()), mxs(g.size()), top(g.size()), pa(g.size()), dep(g.size()),
        dfc(0), tin(g.size()), tou(g.size()), ord(g.size()),
        totsum(0), sum(g.size() + 1) {
        get_size(0, -1);
        make_chain(0, -1, 0);
    }

    void get_size(int i, int f) {
        sz[i] = 1; mxs[i] = -1;
        for (int j: g[i]) {
            if (j == f) continue;
            pa[j] = i;
            dep[j] = dep[i] + 1;
            get_size(j, i);
            sz[i] += sz[j];
            if (mxs[i] == -1 || sz[mxs[i]] < sz[j])
                mxs[i] = j;
        }
    }

    void make_chain(int i, int f, int t) {
        ord[dfc] = i;
        tin[i] = dfc++;
        top[i] = t;
        if (mxs[i] != -1) make_chain(mxs[i], i, t);
        for (int j: g[i]) {
            if (j == f) continue;
            if (j == mxs[i]) continue;
            make_chain(j, i, j);
        }
        tou[i] = dfc;
    }

    void add_f_query(int u, int d, int coef, int &ans) {
        if (d < 0) return;
        ans += coef * (sz[u] - 1);
        f_qs[tou[u]-1].emplace_back(dep[u] + d + 1, -coef, ans);
        f_qs[tin[u]].emplace_back(dep[u] + d + 1, coef, ans);
        // for (int t = tin[u] + 1; t < tou[u]; t++) {
        //     int v = ord[t];
        //     // if (dep[v] - dep[u] <= d) {
        //     //     ans += coef;
        //     // }
        // }
    }

    void do_f_query(int n) {
        vector<int64_t> cnt(n);
        for (int i = 0; i < n; i++) {
            cnt[ dep[ord[i]] ] += sz[ord[i]];
            for (auto &[d, coef, ans]: f_qs[i])
                ans += coef * (d >= 0 && d < n ? cnt[d] : 0);
        }
    }

    int add_query(int x, int y, int d, int &ans) {
        g_qs[x].emplace_back(d, 1, ans);
        g_qs[y].emplace_back(d, 1, ans);
        if (mxs[x] != -1) add_f_query(mxs[x], d - 1, 1, ans);
        if (mxs[y] != -1) add_f_query(mxs[y], d - 1, 1, ans);
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            int t = top[x];
            add_f_query(t, d - 1, -1, ans);
            add_f_query(mxs[pa[t]], d - 1, 1, ans);
            x = pa[t];
        }
        int z = dep[x] < dep[y] ? x : y;
        g_qs[z].emplace_back(d, -2, ans);
        return z;
    }


    void dfs_g(int i, int f) {
        totsum += sz[i];
        for (int j: g[i]) {
            if (j == f || j == mxs[i]) continue;
            for (int t = tin[j]; t < tou[j]; t++) {
                int u = ord[t];
                sum[ dep[u] - dep[i] ] += sz[u];
            }
        }

        for (auto &[d, coef, ans]: g_qs[i]) {
            int64_t cur = totsum - dep[i] - sum[d + 1];
            debug(ans, coef, cur);
            ans += coef * cur;
        }

        for (int j: g[i]) {
            if (j == f) continue;
            dfs_g(j, i);
        }

        totsum -= sz[i];
        for (int j: g[i]) {
            if (j == f || j == mxs[i]) continue;
            for (int t = tin[j]; t < tou[j]; t++) {
                int u = ord[t];
                sum[ dep[u] - dep[i] ] -= sz[u];
            }
        }
    }

    void solve() {
        dfs_g(0, -1);
        do_f_query(g.size());
    }
};


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }


    int q;
    cin >> q;
    vector<int> ans(q);
    Centroid cent(g);
    HLD hld(g);

    for (int i = 0; i < q; i++) {
        int x, y, d;
        cin >> x >> y >> d;
        --x, --y;
        int z = hld.add_query(x, y, d, ans[i]);
        cent.add_query(z, d, ans[i]);
        debug(x+1, y+1, z+1);
        // hld.add_query(z, d, -2, ans[i]);
        // hld.add_query(x, d, 1, ans[i]);
        // hld.add_query(y, d, 1, ans[i]);
    }

    cent.solve();
    orange(all(ans));

    hld.solve();

    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 11ms
memory: 7364kb

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:

7620
6603
14092
2594
1717
9385
8743
6702
13158
5289
3886
2429
12215
3802
11433
12136
12718
3036
12207
2281
5760
11537
12994
8262
2115
3409
13540
12094
2763
8127
2192
8836
3162
6220
2585
8602
4821
787
2821
10820
8165
2591
2595
11107
13119
4675
11536
12980
3945
2761
3148
1827
2849
6968
12774
10668
372...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 535ms
memory: 72544kb

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:

759
69428
2797
181264
91719
182
32496
199183
6399
15975
11640
119051
236
689
17
9540
41
36592
178938
56
45424
193403
90248
3417
949
102
34135
60471
199861
188090
75088
127
1
6
4
3
3
11
61157
199860
199163
155706
196289
192862
53742
51862
179199
428
196282
199989
3635
26
99007
134461
198159
20382
751...

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 749ms
memory: 197820kb

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:

65454
190036
357161
116281
301958
310180
15709
209342
2451
166313
153308
4315
149727
409443
79772
464370
82407
447028
381249
125033
349579
267828
10004
393003
131603
111883
237347
206646
270032
4502
406997
75797
138707
373325
185597
62854
358761
470940
156226
369853
427647
447927
49019
185025
168621...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%