QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#159740 | #7103. Red Black Tree | ucup-team296# | AC ✓ | 1359ms | 51292kb | C++14 | 9.4kb | 2023-09-02 18:30:09 | 2023-09-02 18:30:09 |
Judging History
answer
#include <bits/stdc++.h>
/**
* Author: Niyaz Nigmatullin
*
*/
using namespace std;
struct edge {
int from;
int to;
int w;
};
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// usage:
// auto fun = [&](int i, int j) { return min(i, j); };
// SparseTable<int, decltype(fun)> st(a, fun);
// or:
// SparseTable<int> st(a, [&](int i, int j) { return min(i, j); });
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
public:
int n;
vector<vector<T>> mat;
F func;
SparseTable(const vector<T>& a, const F& f) : func(f) {
n = static_cast<int>(a.size());
int max_log = 32 - __builtin_clz(n);
mat.resize(max_log);
mat[0] = a;
for (int j = 1; j < max_log; j++) {
mat[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++) {
mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
}
}
}
T get(int from, int to) const {
assert(0 <= from && from <= to && to <= n - 1);
int lg = 32 - __builtin_clz(to - from + 1) - 1;
return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
}
};
string to_string(edge const &a) {
return "edge{from=" + to_string(a.from) + ", to=" + to_string(a.to) + ", w=" + to_string(a.w) + "}";
}
vector<long long> solveSmart(int n, vector<int> reds, vector<vector<edge>> edges, vector<vector<int>> queries) {
vector<int> is_red(n);
for (int &x: reds) {
is_red[x] = 1;
}
vector<int> component_id(n, -1);
int K = 1;
while (1 << K < n) K++;
vector<vector<int>> pp(n, vector<int>(K));
vector<int> en(n), ex(n);
vector<long long> depth(n);
int T = 0;
vector<int> global_parent(n);
function<void(int, int)> global_dfs = [&global_parent, &edges, &global_dfs](int v, int p) {
global_parent[v] = p;
for (auto &e: edges[v]) {
if (e.to != p)
global_dfs(e.to, v);
}
};
global_dfs(0, -1);
function<void(int, int, int, long long)> dfs = [&](int v, int p, int c, long long d) {
component_id[v] = c;
depth[v] = d;
en[v] = T++;
// debug(n, v);
pp[v][0] = (p < 0 ? v : p);
for (int i = 1; i < K; i++) {
pp[v][i] = pp[pp[v][i - 1]][i - 1];
}
for (auto &e : edges[v]) {
if (component_id[e.to] < 0 && !is_red[e.to] && e.to != global_parent[v]) {
dfs(e.to, v, c, d + e.w);
}
}
ex[v] = T;
};
int components = 0;
for (int start : reds) {
T = 0;
dfs(start, -1, components++, 0);
}
auto anc = [&en, &ex](int v, int u) {
return en[v] <= en[u] && ex[u] <= ex[v];
};
auto lca = [&anc, &pp, &K](int v, int u) {
if (anc(v, u)) return v;
for (int i = K - 1; i >= 0; i--) {
if (!anc(pp[v][i], u)) {
v = pp[v][i];
}
}
return pp[v][0];
};
// debug(n);
// debug(component_id);
// debug(depth);
// debug(en);
// debug(ex);
auto solve_for_component = [&](vector<int> vs) {
vector<int> only = vs;
vector<long long> dOnly(only.size());
for (int i = 0; i < (int) only.size(); i++) {
dOnly[i] = depth[only[i]];
}
SparseTable<long long, function<long long(long long, long long)>> table(dOnly, [](long long x, long long y) { return max(x, y); });
// debug(only, dOnly);
long long nop = table.get(0, (int) only.size() - 1);
{
int cnt = (int) vs.size();
for (int i = 0; i + 1 < cnt; i++) {
vs.push_back(lca(vs[i], vs[i + 1]));
}
}
long long best = nop;
for (int v : vs) {
int from = (int) (lower_bound(only.begin(), only.end(), v, [&en](int v, int u) {
return en[v] < en[u];
}) - only.begin());
int to;
{
int left = -1;
int right = (int) only.size();
while (left < right - 1) {
int mid = (left + right) >> 1;
if (en[only[mid]] >= ex[v]) {
right = mid;
} else {
left = mid;
}
}
to = right;
}
// debug(en);
// debug(component_id);
long long res = table.get(from, to - 1) - depth[v];
// debug(table.get(from, to - 1));
// debug(table.get(from, to - 1) - depth[v]);
if (from > 0) {
res = max(res, table.get(0, from - 1));
}
if (to < (int) only.size()) {
res = max(res, table.get(to, (int) only.size() - 1));
}
// debug(v, from, to, only, res);
best = min(best, res);
}
return pair<long long, long long>(nop, best);
};
int q = (int) queries.size();
vector<long long> result(q);
for (int cq = 0; cq < q; cq++) {
vector<int> vs = queries[cq];
sort(vs.begin(), vs.end(), [&component_id, &en](int v, int u) {
if (component_id[v] != component_id[u]) {
return component_id[v] < component_id[u];
}
return en[v] < en[u];
});
vector<pair<long long, long long>> results;
for (int from = 0; from < (int) vs.size(); ) {
int to = from + 1;
while (to < (int) vs.size() && component_id[vs[to]] == component_id[vs[from]]) {
to++;
}
results.push_back(solve_for_component(vector<int>(vs.begin() + from, vs.begin() + to)));
from = to;
}
vector<long long> suffixMax(results.size());
for (int i = (int) results.size() - 1; i >= 0; i--) {
suffixMax[i] = results[i].first;
if (i + 1 < (int) results.size()) {
suffixMax[i] = max(suffixMax[i + 1], suffixMax[i]);
}
}
long long current_max = 0;
long long ans = 1LL << 60;
for (int i = 0; i < (int) results.size(); i++) {
long long cur = current_max;
if (i + 1 < (int) results.size()) cur = max(cur, suffixMax[i + 1]);
cur = max(cur, min(results[i].first, results[i].second));
ans = min(ans, cur);
current_max = max(current_max, results[i].first);
}
result[cq] = ans;
}
return result;
}
vector<long long> solveStupid(int n, vector<int> reds, vector<vector<edge>> edges, vector<vector<int>> queries) {
vector<int> is_red(n);
for (int i : reds) is_red[i] = true;
int q = (int) queries.size();
vector<long long> ans(q);
// debug(edges);
auto get_ans = [&](vector<int> const &vs) {
vector<long long> depth(n);
function<void(int, int, long long)> dfs = [&](int v, int p, long long d) {
// debug(v, p, d);
// debug(edges);
if (is_red[v]) d = 0;
depth[v] = d;
for (auto &e : edges[v]) {
if (e.to != p) {
dfs(e.to, v, d + e.w);
}
}
};
dfs(0, -1, 0);
long long res = 0;
for (int v : vs) {
res = max(res, depth[v]);
}
return res;
};
for (int cq = 0; cq < q; cq++) {
auto &vs = queries[cq];
long long cur_ans = get_ans(vs);
for (int change = 0; change < n; change++) {
if (is_red[change]) continue;
is_red[change] = true;
cur_ans = min(cur_ans, get_ans(vs));
is_red[change] = false;
}
ans[cq] = cur_ans;
}
return ans;
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<int> reds(m);
for (int &x: reds) {
cin >> x;
--x;
}
vector<vector<edge>> edges(n);
for (int i = 0; i + 1 < n; i++) {
int from, to, w;
cin >> from >> to >> w;
--from;
--to;
edges[from].push_back({from, to, w});
edges[to].push_back({to, from, w});
}
vector<vector<int>> queries(q);
for (int i = 0; i < q; i++) {
int cnt;
cin >> cnt;
vector<int> vs(cnt);
for (int &x: vs) {
cin >> x;
--x;
}
queries[i] = std::move(vs);
}
vector<long long> ans = solveSmart(n, reds, edges, queries);
for (auto &x: ans) {
cout << x << '\n';
}
}
mt19937 rng(787788);
void test() {
for (int it = 0; it < 10000; it++) {
int n = rng() % 15 + 2;
vector<int> is_red(n);
for (int i = 0; i < n; i++) {
is_red[i] = i == 0 || rng() % 2 == 0;
}
vector<int> reds;
for (int i = 0; i < n; i++) if (is_red[i]) reds.push_back(i);
vector<vector<edge>> edges(n);
vector<int> p(n);
iota(p.begin(), p.end(), 0);
shuffle(p.begin() + 1, p.end(), rng);
for (int i = 1; i < n; i++) {
int to = rng() % i;
int w = rng() % 1000 + 999999000;
edges[p[to]].push_back({p[to], p[i], w});
edges[p[i]].push_back({p[i], p[to], w});
}
for (int i = 0; i < n; i++) {
shuffle(edges[i].begin(), edges[i].end(), rng);
}
assert(p[0] == 0);
int m = rng() % 100 + 1;
vector<vector<int>> queries(m);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rng() % 2 == 0) {
queries[i].push_back(j);
}
}
if (queries[i].empty()) {
queries[i].push_back(rng() % n);
}
}
auto ans1 = solveSmart(n, reds, edges, queries);
auto ans2 = solveStupid(n, reds, edges, queries);
if (ans1 != ans2) {
debug(ans1, ans2);
cout << n << ' ' << reds.size() << ' ' << m << endl;
for (int i : reds) cout << (i + 1) << ' ';
cout << '\n';
for (int i = 0; i < n; i++) {
for (auto &e: edges[i]) {
if (i < e.to) {
cout << i + 1 << ' ' << e.to + 1 << ' ' << e.w << endl;
}
}
}
for (auto &f: queries) {
cout << f.size();
for (auto x : f) cout << " " << x;
cout << endl;
}
assert(ans1 == ans2);
}
assert(ans1 == ans2);
}
}
int main() {
std::cin.tie(NULL); std::ios::sync_with_stdio(false);
// test();
int t;
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: 3632kb
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: 1359ms
memory: 51292kb
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