QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#159621#7103. Red Black Treeucup-team1191#AC ✓1015ms50368kbC++209.3kb2023-09-02 18:11:552023-09-02 18:11:56

Judging History

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

  • [2023-09-02 18:11:56]
  • 评测
  • 测评结果:AC
  • 用时:1015ms
  • 内存:50368kb
  • [2023-09-02 18:11:55]
  • 提交

answer

/*
    author:  Maksim1744
    created: 02.09.2023 12:18:00
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

template<typename T>
struct fenwick {
    vector<T> tree;
    int n;
    int K;

    fenwick(int n = 0) : n(n) {
        tree.assign(n, 0);
        K = 0;
        while ((1 << K) <= n)
            ++K;
    }

    void add(int i, T k) {
        for (; i < n; i = (i | (i + 1)))
            tree[i] += k;
    }

    T ask(int r) {
        T res = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            res += tree[r];
        return res;
    }

    T ask(int l, int r) {
        if (l > r) return 0;
        return ask(r) - ask(l - 1);
    }

    // find first i such that sum[0..i] >= x
    int lower_bound(T x) {
        int cur = 0;
        T cur_sum = 0;
        for (int k = K - 1; k >= 0; --k) {
            int ind = cur | ((1 << k) - 1);
            if (ind >= n) continue;
            if (cur_sum + tree[ind] >= x) continue;
            cur_sum += tree[ind];
            cur |= (1 << k);
        }
        return cur;
    }
};

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
// auto gcd = std::y_combinator([](auto gcd, int a, int b) -> int {
//     return b == 0 ? a : gcd(b, a % b);
// });

vector<int> lca_ind;
vector<vector<int>> lca_sparse;
vector<int> lca_p2;
vector<int> lca_depth;
void build_lca_sparse(vector<vector<pair<int, int>>>& g, int root = 0) {
    int n = g.size();
    vector<int> euler;
    lca_ind.resize(n);
    lca_depth.assign(n, -1);
    function<void(int, int)> dfs = [&](int v, int depth) {
        lca_ind[v] = euler.size();
        euler.pb(v);
        lca_depth[v] = depth;
        for (auto [k, w] : g[v]) {
            if (lca_depth[k] == -1) {
                dfs(k, depth + 1);
                euler.pb(v);
            }
        }
    };
    dfs(root, 0);
    int m = euler.size();
    int log = 1;
    while ((1 << log) < m)
        ++log;
    lca_sparse.resize(log);
    lca_sparse[0].resize(m);
    lca_p2.resize(m + 1);
    int pp2 = 0;
    for (int i = 1; i < lca_p2.size(); ++i) {
        if (1 << (pp2 + 1) <= i)
            ++pp2;
        lca_p2[i] = pp2;
    }
    lca_p2[0] = 0;
    for (int i = 0; i < m; ++i)
        lca_sparse[0][i] = euler[i];
    for (int i = 1; i < log; ++i) {
        lca_sparse[i].assign(m, 0);
        for (int j = 0; j < m - (1 << (i - 1)); ++j) {
            int v1 = lca_sparse[i - 1][j], v2 = lca_sparse[i - 1][j + (1 << (i - 1))];
            if (lca_depth[v1] < lca_depth[v2])
                lca_sparse[i][j] = v1;
            else
                lca_sparse[i][j] = v2;
        }
    }
}

int get_lca(int u, int v) {
    if (u == v)
        return u;
    u = lca_ind[u];
    v = lca_ind[v];
    if (u > v)
        swap(u, v);
    int v1 = lca_sparse[lca_p2[v - u + 1]][u], v2 = lca_sparse[lca_p2[v - u + 1]][v - (1 << lca_p2[v - u + 1]) + 1];
    if (lca_depth[v1] < lca_depth[v2])
        return v1;
    else
        return v2;
}

int dist(int u, int v) {
    return lca_depth[u] + lca_depth[v] - 2 * lca_depth[get_lca(u, v)];
}

void test_case(int test) {
    int n, m, q;
    cin >> n >> m >> q;
    vector<bool> red(n, false);
    for (int i = 0; i < m; ++i) {
        int r;
        cin >> r;
        --r;
        red[r] = true;
    }
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        int w;
        cin >> w;
        g[u].eb(v, w);
        g[v].eb(u, w);
    }

    vector<fenwick<int>> trees(n);
    vector<pair<int, int>> where(n);
    vector<int> upb(n);
    vector<vector<int>> inhere(n);
    vector<ll> score(n);
    vector<ll> h(n);
    vector<int> ind(n);
    vector<int> L(n), R(n);
    vector<int> order;
    vector<int> tin(n), tout(n);
    int tm = 0;

    y_combinator([&](auto dfs, int v, int lastr, int lastb, int p) -> void {
        if (red[v]) lastr = v;
        else lastb = v;
        upb[v] = lastb;
        tin[v] = tm++;
        ind[v] = L[v] = R[v] = order.size();
        if (!red[v]) {
            score[v] = h[v] - h[lastr];
            where[v] = {lastr, inhere[lastr].size()};
            inhere[lastr].pb(ind[v]);
        }
        order.pb(v);
        for (auto [k, w] : g[v]) {
            if (k == p) continue;
            h[k] = h[v] + w;
            dfs(k, lastr, lastb, v);
            R[v] = R[k];
        }
        tout[v] = tm++;
    })(0, -1, -1, -1);

    for (int i = 0; i < n; ++i) {
        trees[i] = fenwick<int>(inhere[i].size());
    }

    build_lca_sparse(g, 0);
    vector<bool> u(n, false);
    vector<vector<pair<int, ll>>> g0(n);
    const ll inf = 1e18;

    vector<pair<ll, ll>> dp0(n, {0, -inf});
    vector<pair<ll, ll>> dp1(n, {0, -inf});

    while (q--) {
        shows;
        int k;
        cin >> k;
        vector<int> vs(k);
        cin >> vs;
        --vs;
        sort(vs.begin(), vs.end(), [&](int u, int v) {
            return ind[u] < ind[v];
        });
        vector<int> cand = vs;
        for (int i = 0; i < vs.size(); ++i) {
            cand.pb(get_lca(vs[i], vs[(i + 1) % vs.size()]));
        }
        cand.pb(0);
        sort(cand.begin(), cand.end());
        cand.erase(unique(cand.begin(), cand.end()), cand.end());

        ll ans = 0;
        for (int v : vs)
            ans = max(ans, score[v]);
        if (ans == 0) {
            cout << ans << '\n';
            continue;
        }
        int vmx = 0;
        for (int v : vs)
            if (score[v] == ans)
                vmx = v;

        int upred = where[vmx].first;

        vector<pair<ll, int>> cur;
        ll other = 0;
        set<pair<ll, int>> left;
        left.emplace(0, -1);
        for (int v : vs) {
            if (red[v]) continue;
            if (where[v].first == upred) {
                cur.eb(h[get_lca(vmx, v)], v);
                left.emplace(score[v], v);
            } else {
                other = max(other, score[v]);
            }
        }
        show(cur);
        show(other);
        sort(cur.begin(), cur.end());
        reverse(cur.begin(), cur.end());
        int lca = vmx;
        for (auto [_, v] : cur) {
            lca = get_lca(lca, v);
            left.erase({score[v], v});
            ans = min(ans, max({other, left.rbegin()->first, h[vmx] - h[lca]}));
            show(left, lca, ans);
        }
        cout << ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T;
    cin >> T;
    for (int test = 1; test <= T; ++test) {
        test_case(test);
    }

    return 0;
}

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

详细

Test #1:

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

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: 1015ms
memory: 50368kb

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