QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#158380#7103. Red Black Treeucup-team045#AC ✓994ms31272kbC++208.6kb2023-09-02 16:28:202023-09-02 16:28:21

Judging History

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

  • [2023-09-02 16:28:21]
  • 评测
  • 测评结果:AC
  • 用时:994ms
  • 内存:31272kb
  • [2023-09-02 16:28:20]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#include<array>
using namespace std;
using LL = long long;

// 1_based HLD
struct Edge{
    int to;
    LL w;
    operator int() const { return to; }
};

struct HLD{
    int n;
    vector<int> sz, top, dep, fa, in, out, seq;
    vector<LL> dis;
    vector<vector<Edge> > g;
    int ts;

    HLD(const vector<vector<Edge> > &g, int root = 1) : n(int(g.size()) - 1), g(g)  {
        ts = 0;
        sz.resize(n + 1);
        top.resize(n + 1);
        dep.resize(n + 1);
        fa.resize(n + 1);
        in.resize(n + 1);
        out.resize(n + 1);
        seq.resize(n + 1);
        dis.resize(n + 1);
        dis[root] = 0;
        dep[root] = 1;
        top[root] = root;
        dfs_sz(root);
        dfs_hld(root);
    }

    void dfs_sz(int u){
        if (fa[u]){
            for(auto it = g[u].begin(); it != g[u].end(); it++){
                if (*it == fa[u]){
                    g[u].erase(it);
                    break;
                }
            }
        }
        sz[u] = 1;
        for(auto &j : g[u]){
            fa[j] = u;
            dep[j] = dep[u] + 1;
            dis[j] = dis[u] + j.w;
            dfs_sz(j);
            sz[u] += sz[j];
            if (sz[j] > sz[g[u][0]])
                swap(j, g[u][0]);
        }
    }

    void dfs_hld(int u){
        in[u] = ++ts;
        seq[in[u]] = u;
        for (auto j : g[u]){
            top[j] = (j == g[u][0] ? top[u] : j);
            dfs_hld(j);
        }
        out[u] = ts;
    }

    int lca(int u, int v){
        while (top[u] != top[v]){
            if (dep[top[u]] > dep[top[v]]){
                u = fa[top[u]];
            } 
            else{
                v = fa[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }

    LL dist(int u, int v){
        return dis[u] + dis[v] - 2 * dis[lca(u, v)];
    }

    bool in_subtree(int u, int v){
        return in[v] <= in[u] && in[u] <= out[v];
    }
    
    int jump(int u, int k) {
        if (dep[u] < k){
            return -1;
        }
        int d = dep[u] - k;
        while (dep[top[u]] > d){
            u = fa[top[u]];
        }
        return seq[in[u] - dep[u] + d];
    }
    
    int rooted_lca(int a, int b, int c){
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }

    template<typename Q>
    void modify_path(int u, int v, const Q &q, bool edge = false){
        while(top[u] != top[v]){
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            q(in[top[u]], in[u]);
            u = fa[top[u]];        
        }
        if (dep[u] > dep[v]) swap(u, v);
        q(in[u] + edge, in[v]);
    }

    template<typename Q>
    void modify_subtree(int u, const Q &q){
        q(in[u], out[u]);
    }  

    template<typename T, typename Q>
    T query_path(int u, int v, const Q &q, bool edge = false){
        T ret = T();
        while(top[u] != top[v]){
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            ret = q(in[top[u]], in[u]) + ret;
            u = fa[top[u]];
        }
        if (dep[u] > dep[v]) swap(u, v);
        return q(in[u] + edge, in[v]) + ret;
    }

    template<typename T, typename Q>
    T query_subtree(int u, const Q &q){
        return q(in[u], out[u]);
    }

    template<typename T, typename Q, typename F>
    T query_path_noncommutative(int u, int v, const Q &q, const F &f, bool edge = false){
        T left = T(), right = T();
        while(top[u] != top[v]){
            if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(left, right);
            left = q(in[top[u]], in[u]) + left;
            u = fa[top[u]];
        }
        if (dep[u] > dep[v]) swap(u, v), swap(left, right);
        return f(left, q(in[u] + edge, in[v]) + right);
    }

};

int stk[2000005];

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n, m, q;
        cin >> n >> m >> q;
        vector<vector<Edge> > g(n + 1);
        vector<bool> red(n + 1);
        for(int i = 0; i < m; i++){
            int x;
            cin >> x;
            red[x] = true;
        }
        for(int i = 0; i < n - 1; i++){
            int a, b, c;
            cin >> a >> b >> c;
            g[a].push_back({b, c});
            g[b].push_back({a, c});
        }
        HLD hld(g);

        vector<LL> f(n + 1);

        auto dfs = [&](auto &&dfs, int u, int fa, LL up) -> void {
            if (red[u]) up = u;
            f[u] = up;
            for(auto &j : g[u]){
                if (j == fa) continue;
                dfs(dfs, j, u, up);
            }
        };

        dfs(dfs, 1, -1, 0);

        vector<vector<int> > ng(n + 1);
        vector<int> in(n + 1), out(n + 1);
        vector<bool> v(n + 1);

        while(q--){
            int k;
            cin >> k;
            vector<int> p(k);
            LL ans = 0;
            for(int i = 0; i < k; i++){
                cin >> p[i], v[p[i]] = true;
                ans = max(ans, hld.dis[p[i]] - hld.dis[f[p[i]]]);
            }
            
            sort(p.begin(), p.end(), [&](int a, int b){
                return hld.in[a] < hld.in[b];
            });

            int top = 0;
            stk[++top] = 1;
            ng[1].clear();
            for(auto x : p){
                if (x != 1){
                    int p = hld.lca(x, stk[top]);
                    if (p != stk[top]){
                        while (hld.in[p] < hld.in[stk[top - 1]]){
                            ng[stk[top - 1]].push_back(stk[top]), top--;
                            // cout << stk[top - 1] << ' ' << stk[top] << '\n';
                        }
                        if (hld.in[p] != hld.in[stk[top - 1]]){
                            ng[p].clear();
                            ng[p].push_back(stk[top]);
                            // cout << p << ' ' << stk[top] << '\n';
                            top--;
                            stk[++top] = p;
                        }
                        else{
                            int t = stk[top--];
                            ng[p].push_back(t);
                            // cout << p << ' ' << t << '\n';
                        } 
                    }
                    ng[x].clear(), stk[++top] = x;
                }
            }
            for(int i = 1; i < top; i++){
                ng[stk[i]].push_back(stk[i + 1]);
                // cout << stk[i] << ' ' << stk[i + 1] << '\n';
            }

            int ts = 0;
            vector<int> seq{0};

            auto dfs1 = [&](auto &&dfs1, int u) -> void {
                in[u] = ++ts;
                seq.push_back(u);
                for(auto &j : ng[u]){
                    dfs1(dfs1, j);
                }
                out[u] = ts;
            };

            dfs1(dfs1, 1);

            vector<LL> pre(ts + 2), suf(ts + 2);
            for(int i = 1; i <= ts; i++){
                if (v[seq[i]]){
                    pre[i] = suf[i] = hld.dis[seq[i]] - hld.dis[f[seq[i]]];
                }
            }
            for(int i = 1; i <= ts; i++)
                pre[i] = max(pre[i - 1], pre[i]);
            for(int i = ts; i >= 1; i--)
                suf[i] = max(suf[i + 1], suf[i]);

            // mx1: 最大的已有祖先的答案
            // mx2: 最大的还没有祖先的答案
            auto dfs2 = [&](auto &&dfs2, int u) -> pair<LL, LL> {
                LL mx1 = 0, mx2 = 0;
                if (v[u]) mx2 = hld.dis[u];
                for(auto &j : ng[u]){
                    auto [t1, t2] = dfs2(dfs2, j);
                    if (hld.dep[f[j]] > hld.dep[u]){
                        mx1 = max(mx1, t1);
                        mx1 = max(mx1, t2 - hld.dis[f[j]]);
                    }
                    else{
                        mx1 = max(mx1, t1);
                        mx2 = max(mx2, t2);
                    }
                }
                if (red[u]){
                    return {max(mx1, mx2 - hld.dis[u]), 0};
                }
                int L = in[u], R = out[u];
                LL cur = max(pre[L - 1], suf[R + 1]);
                cur = max(cur, mx1);
                cur = max(cur, mx2 - hld.dis[u]);
                ans = min(ans, cur);
                return {mx1, mx2};
            };

            dfs2(dfs2, 1);

            for(auto x : p) v[x] = false;
            cout << ans << '\n';
        }
    }

}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3672kb

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: 0
Accepted
time: 994ms
memory: 31272kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

148616264
148616264
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

ok 577632 lines

Extra Test:

score: 0
Extra Test Passed