QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#158343#7103. Red Black Treeucup-team1055#AC ✓1130ms52320kbC++176.2kb2023-09-02 16:26:402023-09-02 16:26:41

Judging History

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

  • [2023-09-02 16:26:41]
  • 评测
  • 测评结果:AC
  • 用时:1130ms
  • 内存:52320kb
  • [2023-09-02 16:26:40]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<class T>
void debug(const T &a) {
    std::cerr << "[debug]" << a << std::endl;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &a) {
    rep(i,0,a.size()) {
        os << a[i] << (i + 1 == (int)a.size() ? "" : " ");
    }
    return os;
}

template<class T>
bool chmin(T &a, T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

template<class T>
bool chmax(T &a, T b) {
    if(a >= b) return false;
    a = b;
    return true;
}

template<class Band, Band (*op)(Band, Band)>
struct sparse_table {
public:
    sparse_table() = default;

    void build(const std::vector<Band> &a) {
        n = (int)a.size();
        table = std::vector(std::__lg(n) + 1, std::vector<Band>(n));
        for(int i = 0; i < n; i++) {
            table[0][i] = a[i];
        }
        for(int k = 1; (1<<k) <= n; k++) {
            for(int i = 0; i + (1 << k) <= n; i++) {
                table[k][i] = op(table[k-1][i], table[k-1][i + (1<<(k-1))]);
            }
        }
    }

    Band fold(int l, int r) {
        int k = std::__lg(r - l);
        return op(table[k][l], table[k][r - (1<<k)]);
    }
private:
    int n;
    std::vector<std::vector<Band>> table;
};

std::pair<int,int> op(std::pair<int,int> lhs, std::pair<int,int> rhs) {
    return lhs.second < rhs.second ? lhs : rhs;
}

void solve() {
    int n,m,q;
    std::cin >> n >> m >> q;
    std::vector tree(n, std::vector<std::pair<int,ll>>());
    std::vector<int> color(n, 0);
    rep(i,0,m) {
        int r;
        std::cin >> r;
        r--;
        color[r] = 1;
    }
    rep(i,0,n-1) {
        int u, v;
        ll w;
        std::cin >> u >> v >> w;
        u--; v--;
        tree[u].emplace_back(v, w);
        tree[v].emplace_back(u, w);
    }
    std::vector<int> in, out;
    std::vector<int> id(n);
    std::vector<int> cnt(n, 0);
    std::vector<std::pair<int,int>> vs;
    std::vector<ll> dist(n, 0);
    std::vector<ll> cost(n);
    {
        auto euler_tour_dfs = [&](auto &&self, int v, int par, int d, ll red) -> void {
            id[v] = int(vs.size());
            vs.emplace_back(v, d);
            if(color[v] == 1) chmax(red, dist[v]);
            cost[v] = dist[v] - red;
            if(color[v] == 1) cnt[v]++;
            for(auto [nv, w]: tree[v]) {
                if(nv == par) continue;
                dist[nv] = dist[v] + w;
                cnt[nv] = cnt[v];
                self(self, nv, v, d + 1, red);    
                vs.emplace_back(v, d);
            }
        };
        euler_tour_dfs(euler_tour_dfs, 0, -1, 0, 0);
    }
    sparse_table<std::pair<int,int>, op> st;
    st.build(vs);
    auto lca = [&](int u, int v) -> int {
        u = id[u];
        v = id[v];
        if(u > v) std::swap(u, v);
        return st.fold(u, v + 1).first;
    };
    std::vector<int> rev(n, -1), mark(n, -1);
    while(q--) {
        int k;
        std::cin >> k;
        std::vector<int> vk(k);
        for(auto &v: vk) {
            std::cin >> v;
            v--;
            assert(0 <= v && v < n);
            mark[v] = 1;
        }
        std::vector<int> s;
        std::vector<std::vector<int>> auxiliary_tree;
        int sz;
        std::vector<ll> cost_a;
        {
            std::sort(all(vk), [&](int u, int v) -> bool { return id[u] < id[v]; });
            s = vk;
            rep(i,0,k-1) {
                s.emplace_back(lca(vk[i], vk[i+1]));
            }
            s.emplace_back(0);
            std::sort(all(s), [&](int u, int v) -> bool { return id[u] < id[v]; });
            s.erase(std::unique(all(s)), s.end());
            sz = s.size();
            auxiliary_tree.resize(sz);
            cost_a.resize(sz);
            rep(i,0,sz) {
                int v = s[i];
                rev[v] = i;
                if(mark[v] > 0) cost_a[i] = cost[v];
            }
            rep(i,0,sz-1) {
                int l = lca(s[i], s[i+1]);
                int u = rev[l];
                int v = rev[s[i+1]];
                auxiliary_tree[u].emplace_back(v);
                auxiliary_tree[v].emplace_back(u);
            }
        }
        int root = rev[0];
        std::vector<int> in(sz), out(sz);
        {
            int t = 0;
            auto euler_tour_dfs = [&](auto &&self, int v, int par = -1) -> void {
                in[v] = t++;
                for(auto nv: auxiliary_tree[v]) {
                    if(nv == par) continue;
                    self(self, nv, v);
                }
                out[v] = t;
            };
            euler_tour_dfs(euler_tour_dfs, root);
        }
        std::vector<ll> left_max(sz+1, 0), right_max(sz+1, 0);
        rep(i,0,sz) {
            left_max[i+1] = right_max[i] = cost_a[in[i]];
        }
        rep(i,0,sz) {
            chmax(left_max[i+1], left_max[i]);
        }
        rrep(i,0,sz) {
            chmax(right_max[i], right_max[i+1]);
        }
        ll ans = std::numeric_limits<ll>::max();
        auto dfs = [&](auto &&self, int v, int par = -1) -> std::tuple<ll,ll,ll> {
            ll a = dist[s[v]], b = 0, c = cost_a[v];
            for(auto nv: auxiliary_tree[v]) {
                if(nv == par) continue;
                auto [s_a, s_b, s_c] = self(self, nv, v);
                if(cnt[s[nv]] - cnt[s[v]] > 0) {
                    s_a = 0;
                    s_b = s_c;
                }
                chmax(a, s_a);
                chmax(b, s_b);
                chmax(c, s_c);
            }
            ll ret = std::max(a - dist[s[v]], b);
            chmax(ret, left_max[in[v]]);
            chmax(ret, right_max[out[v]]);
            chmin(ans, ret);
            return {a, b, c};
        };
        dfs(dfs, root);
        std::cout << ans << '\n';
        for(auto v: vk) mark[v] = -1;
    }
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int t;
    std::cin >> t;
    while(t--) {
        solve();
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3680kb

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: 1130ms
memory: 52320kb

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