QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302301#7103. Red Black Treeluhanning#AC ✓950ms38812kbC++205.9kb2024-01-10 18:55:402024-01-10 18:55:40

Judging History

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

  • [2024-01-10 18:55:40]
  • 评测
  • 测评结果:AC
  • 用时:950ms
  • 内存:38812kb
  • [2024-01-10 18:55:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 2e5 + 10;
struct HLD {
    int n;
    std::vector<int> siz, top, dep, parent, in, out, seq;
    std::vector<std::vector<int>> g;
    int cur;
    
    HLD() {}
    HLD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        cur = 0;
        g.assign(n, {});
    }
    void addEdge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void work(int root = 0) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        if (parent[u] != -1) {
            g[u].erase(std::find(g[u].begin(), g[u].end(), parent[u]));
        }
        
        siz[u] = 1;
        for (auto &v : g[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[g[u][0]]) {
                std::swap(v, g[u][0]);
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : g[u]) {
            top[v] = v == g[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }
    
    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    
    int jump(int u, int k) {
        if (dep[u] < k) {
            return -1;
        }
        
        int d = dep[u] - k;
        
        while (dep[top[u]] > d) {
            u = parent[top[u]];
        }
        
        return seq[in[u] - dep[u] + d];
    }
    
    bool isAncester(int u, int v) {
        return in[u] <= in[v] && in[v] < out[u];
    }
    
    int rootedParent(int u, int v) {
        std::swap(u, v);
        if (u == v) {
            return u;
        }
        if (!isAncester(u, v)) {
            return parent[u];
        }
        auto it = std::upper_bound(g[u].begin(), g[u].end(), v, [&](int x, int y) {
            return in[x] < in[y];
        }) - 1;
        return *it;
    }
    
    int rootedSize(int u, int v) {
        if (u == v) {
            return n;
        }
        if (!isAncester(v, u)) {
            return siz[v];
        }
        return n - siz[rootedParent(u, v)];
    }
    
    int rootedLca(int a, int b, int c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
};//从0开始
void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> red(n);
    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        x--;
        red[x] = 1;
    }
    vector<vector<pair<int, int>>> g(n + 1);
    vector<vector<int>> G(n + 1); 
    HLD h(n);
    for(int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        G[u].push_back(v);
        G[v].push_back(u);
    }
    h.g = G;
    h.work();
    vector<ll> dis(n), cost(n);
    
    function<void(int, int, int)> dfs = [&](int u, int fa, int lastRed) {
        if(red[u]) lastRed = u;
        //cout << u << ' ' << lastRed << '\n';
        cost[u] = dis[u] - dis[lastRed];
        for(auto [v, w] : g[u]) {
            if(v == fa) continue;
            dis[v] = dis[u] + w;
            dfs(v, u, lastRed); 
        }
    };
    dfs(0, -1, -1);
    // cout << "bug:\n";
    // for(int i = 0; i < n; i++) cout << i << ' ' << cost[i] << '\n';
    // cout << '\n';
    vector<vector<int>> son(n); 
    while(q--) {
        int k;
        cin >> k;
        vector<int> a(k);
        multiset<ll> st;
        for(int i = 0; i < k; i++) {
            cin >> a[i];
            a[i]--;
            st.insert(cost[a[i]]);
        }
        sort(a.begin(), a.end(), [&](int x, int y) {
            if(cost[x] == cost[y]) return h.dep[x] > h.dep[y];
            else return cost[x] > cost[y];
        });
        ll ans = cost[a[0]];
        // for(int i = 0; i < k; i++) {
        //     cout << i << ' ' << a[i] << ' ' << cost[a[i]] << "\n";
        // }
        //cout << a[0] << '\n';
        vector<int> anc;
        for(int i = 0; i < k; i++) {
            int ancester = h.lca(a[0], a[i]);
            if(red[ancester] == 1) continue;
            if(ancester == a[0]) {
                if(i != 0) continue;
            }
            if(dis[a[0]] - dis[ancester] >= cost[a[0]]) continue;
            if(cost[a[i]] < dis[a[i]] - dis[ancester]) continue;
            anc.push_back(ancester);
            son[ancester].push_back(a[i]);
            //cout << ancester << '\n';
        }
        sort(anc.begin(), anc.end(), [&](int x, int y) {
            return h.dep[x] > h.dep[y];
        });
        for(int i = 0; i < anc.size(); i++) {
            if(i && anc[i] == anc[i - 1]) continue;
            for(int j : son[anc[i]]) {
                auto pos = st.lower_bound(cost[j]);
                st.erase(pos);
            }
            son[anc[i]].clear();
            ll result1 = dis[a[0]] - dis[anc[i]], result2 = 0;
            if(!st.empty()) {
                result2 = *st.rbegin();
            }
            ans = min(ans, max(result1, result2));
            //cout << anc[i] << ' ' << max(result1, result2) << '\n';
        }
        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    t = 1;
    cin >> t;
    while(t--) {
        solve();
    }

    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3496kb

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: 950ms
memory: 38812kb

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