QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#159621 | #7103. Red Black Tree | ucup-team1191# | AC ✓ | 1015ms | 50368kb | C++20 | 9.3kb | 2023-09-02 18:11:55 | 2023-09-02 18:11:56 |
Judging History
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,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
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